Hamiltonian paths in some classes of grid graphs. (English) Zbl 1245.05081

Summary: The Hamiltonian path problem for general grid graphs is known to be NP-complete. In this paper, we give necessary and sufficient conditions for the existence of Hamiltonian paths in \(L\)-alphabet, \(C\)-alphabet, \(F\)-alphabet, and \(E\)-alphabet grid graphs. We also present linear-time algorithms for finding Hamiltonian paths in these graphs.


05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI arXiv


[1] R. Diestel, Graph Theory, vol. 173, Springer, New York, NY, USA, 2nd edition, 2000. · Zbl 0974.46031
[2] M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman and Co., San Francisco, Calif, USA, 1979. · Zbl 0411.68039
[3] P. Damaschke, “Paths in interval graphs and circular arc graphs,” Discrete Mathematics, vol. 112, no. 1-3, pp. 49-64, 1993. · Zbl 0777.05081
[4] L. Du, “A polynomial time algorithm for hamiltonian cycle (Path),” in Proceedings of the International MultiConference of Engineers and Computer Scientists (IMECS ’10), vol. 1, pp. 17-19, Hong Kong, 2010.
[5] R. J. Gould, “Advances on the Hamiltonian problem-a survey,” Graphs and Combinatorics, vol. 19, no. 1, pp. 7-52, 2003. · Zbl 1024.05057
[6] Y. Gurevich and S. Shelah, “Expected computation time for Hamiltonian path problem,” SIAM Journal on Computing, vol. 16, no. 3, pp. 486-502, 1987. · Zbl 0654.68083
[7] S.-S. Kao and L.-H. Hsu, “Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs,” Applied Mathematics and Computation, vol. 160, no. 1, pp. 269-282, 2005. · Zbl 1057.05052
[8] M. S. Rahman and M. Kaykobad, “On Hamiltonian cycles and Hamiltonian paths,” Information Processing Letters, vol. 94, no. 1, pp. 37-41, 2005. · Zbl 1182.68142
[9] F. Luccio and C. Mugnia, “Hamiltonian paths on a rectangular chessboard,” in Proceedings of the 16th Annual Allerton Conference, pp. 161-173, 1978.
[10] A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, “Hamilton paths in grid graphs,” SIAM Journal on Computing, vol. 11, no. 4, pp. 676-686, 1982. · Zbl 0506.05043
[11] C. Zamfirescu and T. Zamfirescu, “Hamiltonian properties of grid graphs,” SIAM Journal on Discrete Mathematics, vol. 5, no. 4, pp. 564-570, 1992. · Zbl 0770.05073
[12] S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Computing. Theory and Applications, vol. 28, no. 9, pp. 1293-1305, 2002. · Zbl 0999.68253
[13] W. Lenhart and C. Umans, “Hamiltonian cycles in solid grid graphs,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97), pp. 496-505, 1997.
[14] A. N. M. Salman, Contributions to graph theory, Ph.D. thesis, University of Twente, 2005.
[15] K. Islam, H. Meijer, Y. Nunez, D. Rappaport, and H. Xiao, “Hamiltonian circuts in hexagonal grid graphs,” in Proceedings of the CCCG, pp. 20-22, 2007.
[16] V. S. Gordon, Y. L. Orlovich, and F. Werner, “Hamiltonian properties of triangular grid graphs,” Discrete Mathematics, vol. 308, no. 24, pp. 6166-6188, 2008. · Zbl 1158.05040
[17] M. Nandi, S. Parui, and A. Adhikari, “The domination numbers of cylindrical grid graphs,” Applied Mathematics and Computation, vol. 217, no. 10, pp. 4879-4889, 2011. · Zbl 1223.05214
[18] F. Keshavarz-Kohjerdi, A. Bagheri, and A. Asgharian-Sardroud, “A linear-time algorithm for the longest path problem in rectangular grid graphs,” Discrete Applied Mathematics, vol. 160, no. 3, pp. 210-217, 2012. · Zbl 1237.05115
[19] F. Keshavarz-Kohjerdi and A. Bagheri, “An efficient parallel algorithm for the longest path problem in meshes,” http://arxiv.org/abs/1201.4459. · Zbl 1245.05081
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.