×

zbMATH — the first resource for mathematics

A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole. (English) Zbl 1371.05287
Summary: The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give the necessary conditions for the existence of a Hamiltonian path between two given vertices in a rectangular grid graph with a rectangular hole; where the size of graph is even. In addition, we show that the Hamiltonian path in these graphs can be computed in linear-time.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI
References:
[1] Afrati, F. N., The Hamilton circuit problem on grids, 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] Damasachke, P., The Hamiltonian circuit problem for circle graphs is NP-complete, Inform. Process. Lett., 32, 1-2, (1989)
[4] Du, L., A polynomial time algorithm for Hamiltonian cycle (path), (Proceedings of the International Multiconference of Engineers and Computer Scientists, IMECS (I), (2010)), 17-19
[5] 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
[6] 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
[7] Garey, M. R.; Johnson, D. S.; Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704-714, (1976) · Zbl 0346.05110
[8] Gorbenko, A.; Popov, V.; Sheka, A., Localization on discrete grid graphs, (He, Xingui; Hua, Ertian; Lin, Yun; Liu, Xiaozhu, Computer, Informatics, Cybernetics and Applications, Lect. Notes Electr. Eng., (2012)), 971-978
[9] Gould, R. J., Advances on the Hamiltonian problem: a survey, Graphs Combin., 19, 1, 7-52, (2003) · Zbl 1024.05057
[10] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 24, 6166-6188, (2008) · Zbl 1158.05040
[11] Hamada, K., A picturesque maze generation algorithm with any given endpoints, J. Inf. Process., 21, 3, 393-397, (2013)
[12] Hung, R. W., Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl. Math., 211, 99-112, (2016) · Zbl 1348.05117
[13] 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
[14] Islam, K.; Meijer, H.; Rodriguez, Y. N.; Rappaport, D.; Xiao, H., Hamiltonian circuits in hexagonal grid graphs, (Proceedings of 19th Canadian Conference of Computational Geometry, CCCG’97, (2007)), 85-88
[15] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[16] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in some classes of grid graphs, J. Appl. Math., (2012) · Zbl 1245.05081
[17] 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
[18] Keshavarz-Kohjerdi, F.; Bagheri, A., A parallel algorithm for the longest path problem in rectangular grid graphs, J. Supercomput., 65, 723-741, (2013)
[19] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in L-shaped grid graphs, Theoret. Comput. Sci., 621, 37-56, (2016) · Zbl 1335.05100
[20] Keshavarz-Kohjerdi, F.; Bagheri, A., A linear-time algorithm for finding Hamiltonian \((s, t)\)-paths in odd-sized rectangular grid graphs with a rectangular hole, J. Supercomput., (2017), in press · Zbl 1371.05287
[21] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in C-shaped grid graphs, submitted for publication, available at · Zbl 1335.05100
[22] 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
[23] Luccio, F.; Mugnia, C., Hamiltonian paths on a rectangular chessboard, (Proceedings of 16th Annual Allerton Conference, (1978)), 161-173
[24] Myers, B. R., Enumeration of tours in Hamiltonian rectangular lattice graphs, Math. Mag., 54, 19-23, (1981) · Zbl 0456.05035
[25] Rahman, M. S.; Kaykobad, M., On Hamiltonian cycles and Hamiltonian paths, Inform. Process. Lett., 94, 1, 37-41, (2005) · Zbl 1182.68142
[26] 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
[27] 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
[28] Zamfirescu, C.; Zamfirescu, T., Hamiltonian properties of grid graphs, SIAM J. Discrete Math., 5, 4, 564-570, (1992) · Zbl 0770.05073
[29] 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.