×

zbMATH — the first resource for mathematics

Hamiltonian paths in \(L\)-shaped grid graphs. (English) Zbl 1335.05100
Summary: Grid graphs are subgraphs of the infinite 2-dimensional integer grid. The Hamiltonian path problem for general grid graphs is a well-known NP-complete problem. In this paper, we present necessary and sufficient conditions for the existence of a Hamiltonian path between two given vertices in \(L\)-shaped grid graphs. We also show that a Hamiltonian path between two given vertices of a \(L\)-shaped grid graph can be computed in linear time.

MSC:
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Afrati, F. N., The Hamilton circuit problem on grids, RAIRO Theor. Inform. Appl., 28, 6, 567-582, (1994) · Zbl 0884.68097
[2] Chen, S. D.; Shen, H.; Topor, R., An efficient algorithm for constructing Hamiltonian paths in meshes, Parallel Comput., 28, 9, 1293-1305, (2002) · Zbl 0999.68253
[3] Du, L., A polynomial time algorithm for Hamiltonian cycle (path), (Proceedings of the International MultiConference of Engineers and Computer Scientists, vol. I, IMECS, (2010)), 17-19
[4] Felsner, S.; Liotta, G.; Wismath, S., Straight-line drawings on restricted integer grids in two and three dimensions, J. Graph Algorithms Appl., 7, 4, 363-398, (2003) · Zbl 1068.68103
[5] Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[6] Gorbenko, A.; Popov, V.; Sheka, A., Localization on discrete grid graphs, (He, Xingui; Hua, Ertian; Lin, Yun; Liu, Xiaozhu, Computer, Informatics, Cybernetics and Applications, Lecture Notes in Electrical Engineering, (2012)), 971-978
[7] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 24, 6166-6188, (2008) · Zbl 1158.05040
[8] Gould, R. J., Advances on the Hamiltonian problem: a survey, Graphs Combin., 19, 1, 7-52, (2003) · Zbl 1024.05057
[9] Hamada, K., A picturesque maze generation algorithm with any given endpoints, J. Inf. Process., 21, 3, 393-397, (2013)
[10] Icking, C.; Kamphans, T.; Klein, R.; Langetepe, E., Exploring simple grid polygons, (Proceedings of 11th Annual International Computing and Combinatorics Conference, COCOON, (2005)), 524-533 · Zbl 1128.68504
[11] Islam, K.; Meijer, H.; Rodriguez, Y. N.; Rappaport, D.; Xiao, H., Hamiltonian circuts in hexagonal grid graphs, (Proceedings of 19th Canadian Conference of Computational Geometry, CCCG’97, (2007)), 85-88
[12] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[13] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in some classes of grid graphs, J. Appl. Math., 475087, (2012) · Zbl 1245.05081
[14] Keshavarz-Kohjerdi, F.; Bagheri, A.; Asgharian-Sardroud, A., A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 3, 210-217, (2012) · Zbl 1237.05115
[15] Keshavarz-Kohjerdi, F.; Bagheri, A., A parallel algorithm for the longest path problem in rectangular grid graphs, J. Supercomput., 65, 723-741, (2013)
[16] Lenhart, W.; Umans, C., Hamiltonian cycles in solid grid graphs, (Proceedings of 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, (1997)), 496-505
[17] Luccio, F.; Mugnia, C., Hamiltonian paths on a rectangular chessboard, (Proceedings of 16th Annual Allerton Conference, (1978)), 161-173
[18] Myers, B. R., Enumeration of tours in Hamiltonian rectangular lattice graphs, Math. Mag., 54, 19-23, (1981) · Zbl 0456.05035
[19] Rahman, M. S.; Kaykobad, M., On Hamiltonian cycles and Hamiltonian paths, Inform. Process. Lett., 94, 1, 37-41, (2005) · Zbl 1182.68142
[20] Salman, A. N.M.; Broersma, H. J.; Baskoro, E. T., Spanning 2-connected subgraphs in alphabet graphs, special classes of grid graphs, J. Autom. Lang. Comb., 8, 4, 675-681, (2003) · Zbl 1053.05093
[21] Srinivasa Rao, A. S.R.; Tomleyc, F.; Blakec, D., Understanding chicken walks on \(n \times n\) grid: Hamiltonian paths, discrete dynamics, and rectifiable paths, Math. Methods Appl. Sci., 38, 15, 3346-3358, (2015) · Zbl 1330.92137
[22] Zamfirescu, C.; Zamfirescu, T., Hamiltonian properties of grid graphs, SIAM J. Discrete Math., 5, 4, 564-570, (1992) · Zbl 0770.05073
[23] Zhang, W. Q.; Liu, Y. J., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 39, 5340-5350, (2011) · Zbl 1222.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.