期刊名称：IAENG International Journal of Computer Science
印刷版ISSN：1819-656X
电子版ISSN：1819-9224
出版年度：2020
卷号：47
期号：3
语种：English
出版社：IAENG - International Association of Engineers
摘要：Supergrid (or called strong grid) graphs contain grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian (s, t)-path of a graph is a Hamiltonian path between any two distinct vertices s and t in the graph, and the longest (s, t)-path is a simple path with the maximum number of vertices from s to t in the graph. A graph is called Hamiltonian if it contains a Hamiltonian cycle, and is said to be Hamiltonian connected if there exists a Hamiltonian (s, t)-path in it. These problems are known to be NP-complete for general supergrid graphs. As far as we know, their complexities are still unknown for solid supergrid graphs which are supergrid graphs without any hole. In this paper, we will study these problems on L-shaped supergrid graphs which form a subclass of solid supergrid graphs. First, we prove L-shaped supergrid graphs to be Hamiltonian except one trivial condition. We then verify the Hamiltonian connectivity of L-shaped supergrid graphs except few conditions. The Hamiltonicity and Hamiltonian connectivity of L-shaped supergrid graphs can be applied to compute the minimum trace of computerized embroidery machine and 3D printer when a L-like object is printed. Finally, we present a linear-time algorithm to compute the longest (s, t)-paths of Lshaped supergrid graphs. This study can be regarded as the first attempt for solving the Hamiltonian and longest (s, t)-path problems on solid supergrid graphs.
