×

zbMATH — the first resource for mathematics

Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs. (English) Zbl 07172793
Summary: The longest and Hamiltonian path problems are well-known NP-hard problems in graph theory. Despite many applications of these problems, they are still open for many classes of graphs, including solid grid graphs and grid graphs with some holes. We consider the longest and Hamiltonian \((s,t)\)-path problems in \(C\)-shaped grid graphs. A \((s,t)\)-path is a path between two given vertices \(s\) and \(t\) of the graph. A \(C\)-shaped grid graph is a rectangular grid graph such that a rectangular grid subgraph is removed from it to make a \(C\)-liked shape. In this paper, we first give the necessary conditions for the existence of Hamiltonian cycles and Hamiltonian \((s,t)\)-paths in such graphs. Then by given a linear-time algorithm for finding Hamiltonian cycles and Hamiltonian \((s,t)\)-paths, we show that these necessary conditions are also sufficient. Finally, we give a linear-time algorithm for finding the longest \((s,t)\)-path in these graphs.
MSC:
90Cxx Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 676-686 (1982) · Zbl 0506.05043
[2] Lenhart, W.; Umans, C., Hamiltonian cycles in solid grid graphs, (Proceedings of 38th Annual Symposium on Foundations of Computer Science. Proceedings of 38th Annual Symposium on Foundations of Computer Science, FOCS ’97 (1997)), 496-505
[3] Bulterman, R. W.; van der Sommen, F. W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A. J.M.; Feijen, W. H.J., On computing a longest path in a tree, Inf. Process. Lett., 81, 93-96 (2002) · Zbl 1032.68671
[4] Mertzios, G. B.; Corneil, D. G., The longest path problem is polynomial on cocomparability graphs, Algorithmica, 65, 177-205 (2013) · Zbl 1259.68094
[5] Uehara, R.; Uno, Y., On computing longest paths in small graph classes, Internat. J. Found Comput. Sci., 18, 911-930 (2007) · Zbl 1202.68291
[6] Gutin, G., Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math., 6, 270-273 (1993) · Zbl 0773.05071
[7] Karger, D.; Montwani, R.; Ramkumar, G. D.S., On approximating the longest path in a graph, Algorithmica, 18, 82-98 (1997) · Zbl 0876.68083
[8] Björklund, A.; Husfeldt, T., Finding a path of superlogarithmic length, SIAM J. Comput., 32, 1395-1402 (2003) · Zbl 1041.68066
[9] Zhang, Z.; Li, H., Algorithms for long paths in graphs, Theoret. Comput. Sci., 377, 25-34 (2007) · Zbl 1117.68057
[10] 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
[11] Rahman, M. S.; Kaykobad, M., On Hamiltonian cycles and Hamiltonian paths, Inf. Process. Lett., 94, 37-41 (2005) · Zbl 1182.68142
[12] Hamada, K., A picturesque maze generation algorithm with any given endpoints, J. Inf. Process., 21, 393-397 (2013)
[13] 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, 3346-3358 (2015) · Zbl 1330.92137
[14] Icking, C.; Kamphans, T.; Klein, R.; Langetepe, E., Exploring simple grid polygons, (Proceedings of 11th Annual International Computing and Combinatorics Conference (2005)), 524-533 · Zbl 1128.68504
[15] Chen, S. D.; Shen, H.; Topor, R., An efficient algorithm for constructing Hamiltonian paths in meshes, Parallel Comput., 28, 1293-1305 (2002) · Zbl 0999.68253
[16] 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, 675-681 (2003) · Zbl 1053.05093
[17] Keshavarz Kohjerdi, F.; A. Bagheri, H. J., Hamiltonian paths in some classes of grid graphs, J. Appl. Math., Article 475087 pp. (2012), 1-17 · Zbl 1245.05081
[18] Zhang, W. Q.; Liu, Y. J., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 5340-5350 (2011) · Zbl 1222.68089
[19] 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, 210-217 (2012) · Zbl 1237.05115
[20] Keshavarz-Kohjerdi, F.; Bagheri, A., An efficient parallel algorithm for the longest path problem in rectangular grid graphs, J. Supercomput., 65, 723-741 (2013)
[21] Hung, R. W.; Yao, C. C.; Chan, S. J., The Hamiltonian properties of supergrid graphs, Theoret. Comput. Sci., 602, 132-148 (2015) · Zbl 1330.05093
[22] Hung, R. W., Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl. Math., 211, 99-112 (2016) · Zbl 1348.05117
[23] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in \(L\)-shaped grid graphs, Theoret. Comput. Sci., 621, 37-56 (2016) · Zbl 1335.05100
[24] Keshavarz-Kohjerdi, F.; Bagheri, A., Longest \(( s , t )\)-paths in \(L\)-shaped grid graphs, Optim. Methods Softw., 34, 797-826 (2018) · Zbl 1414.05164
[25] Felsner, S.; Liotta, G.; Wismath, S., Straight-line drawings on restricted integer grids in two and three dimensions, J. Graph Algorithms Appl., 7, 363-398 (2003) · Zbl 1068.68103
[26] Keshavarz-Kohjerdi, F.; Bagheri, A., A linear-time algorithm for finding Hamiltonian \(( s , t )\)-paths in even-sized rectangular grid graphs with a rectangular hole, Theoret. Comput. Sci., 690, 26-58 (2017) · Zbl 1371.05287
[27] 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., 73, 3821-3860 (2017) · Zbl 1371.05287
[28] Hung, R. W.; Li, C. F.; Chen, J. S.; Su, Q. S., The Hamiltonian connectivity of rectangular supergrid graphs, Discrete Optim., 26, 41-65 (2017) · Zbl 1387.05140
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.