×

zbMATH — the first resource for mathematics

Longest \((s, t)\)-paths in \(L\)-shaped grid graphs. (English) Zbl 1414.05164
Summary: The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An \(L\)-shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices \(s\) and \(t\) of an \(L\)-shaped grid graph can be computed in linear time.

MSC:
05C38 Paths and cycles
05C12 Distance in graphs
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
References:
[1] Asgharian-Sardroud, A.; Bagheri, A., An approximation algorithm for the longest path problem in solid grid graphs, Optim. Methods Softw., 31, 3, 479-493, (2016) · Zbl 1357.68297
[2] Asgharian-Sardroud, A.; Bagheri, A., An approximation algorithm for the longest cycle problem in solid grid graphs, Discrete Appl. Math., 204, 6-12, (2016) · Zbl 1333.05091
[3] Björklund, A.; Husfeldt, T., Finding a path of superlogarithmic length, SIAM J. Comput., 32, 6, 1395-1402, (2003) · Zbl 1041.68066
[4] 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, 2, 93-96, (2002) · Zbl 1032.68671
[5] 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
[6] Diestel, R., Graph Theory, (2000), Springer: Springer, New York
[7] A polynomial time algorithm for Hamilton cycle (path), Proceedings of the International MultiConference of Engineers and Computer Scientists, IMECS, (I), Hong Kong20101719
[8] 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
[9] Finding long paths and cycle of super polylogarithmic length, 36th Annual ACM Symposium on Theory of Computing, STOC, ACM, Chicago, IL, USA2004407416
[10] Finding long paths, cycle and circuits, in Algorithms and Computation, S. Hong, H. Nagamochi, and T. Fukunaga, eds., Proceedings of 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, Vol. 5369, Springer-Verlag, Berlin2008752763
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979), Freeman: Freeman, San Francisco, CA
[12] Gorbenko, A.; Popov, V.; Sheka, A., Localization on discrete grid graphs, 971-978, (2012)
[13] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 24, 6166-6188, (2008) · Zbl 1158.05040
[14] Guo, Y. L.; Ho, C. W.; Tat Ko, M., The longest path problem on distance-hereditary graphs, Adv. Intell. Syst. Appl. - 1 Smart Innovation Syst. Technol, 20, 69-77, (2013)
[15] Gutin, G., Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math., 6, 2, 270-273, (1993) · Zbl 0773.05071
[16] Hamada, K., A picturesque maze generation algorithm with any given endpoints, J. Inf. Process., 21, 3, 393-397, (2013)
[17] Hung, R. W., Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl. Math., 211, 99-112, (2016) · Zbl 1348.05117
[18] Hung, R. W.; Yao, C. C.; Chen, S. J., The Hamiltonian properties of supergrid graphs, Theor. Comput. Sci., 602, 132-148, (2015) · Zbl 1330.05093
[19] Exploring simple grid polygons, in Computing and Combinatorics, L. Wang, ed., Proceedings of 11th Annual International Conference, COCOON 2005, Kunming, China, August 16–19, Vol. 3595, Springer-Verlag, Berlin2005524533
[20] Hamiltonian circuts in hexagonal grid graphs, Proceedings of 19th Canadian Conference of Computational Geometry, CCCG’97, Ottawa, Canada20078588
[21] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[22] Karger, D.; Montwani, R.; Ramkumar, G. D.S., On approximating the longest path in a graph, Algorithmica, 18, 1, 82-98, (1997) · Zbl 0876.68083
[23] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in some classes of grid graphs, J. Appl. Math, 1-17, (2012) · Zbl 1245.05081
[24] Keshavarz-Kohjerdi, F.; Bagheri, A., An efficient parallel algorithm for the longest path problem in meshes, J. Supercomput., 65, 723-741, (2013)
[25] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in L-shaped grid graphs, Theor. Comput. Sci., 621, 37-56, (2016) · Zbl 1335.05100
[26] Keshavarz-Kohjerdi, F.; Bagheri, A., A linear-time algorithm for finding Hamiltonian \(##?##\)-paths in even-sized rectangular grid graphs with a rectangular hole, Theor. Comput. Sci., 690, 26-58, (2017) · Zbl 1371.05287
[27] Keshavarz-Kohjerdi, F.; Bagheri, A., A linear-time algorithm for finding Hamiltonian \(##?##\)-paths in odd-sized rectangular grid graphs with a rectangular hole, J. Supercomput., 73, 9, 3821-3860, (2017)
[28] 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
[29] Hamiltonian cycles in solid grid graphs, Proceedings of 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, FL, 1997496505
[30] The longest path problem is polynomial on interval graphs, in Mathematical Foundations of Computer Science 2009, R. Královic and D. Niwinski, eds., Proceedings of 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24–28, Vol. 5734, Springer-Verlag, Berlin2009403414
[31] Mertzios, G. B.; Corneil, D. G., The longest path problem is polynomial on cocomparability graphs, Algorithmica, 65, 1, 177-205, (2013) · Zbl 1259.68094
[32] 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
[33] Srinivasa Rao, A. S.R.; Tomleyc, F.; Blakec, D., Understanding chicken walks on \(##?##\) grid: Hamiltonian paths, discrete dynamics, and rectifiable paths, Math. Methods Appl. Sci., 38, 15, 3346-3358, (2015) · Zbl 1330.92137
[34] Uehara, R.; Uno, Y., On computing longest paths in small graph classes, Int. J. Found. Comput. Sci., 18, 5, 911-930, (2007) · Zbl 1202.68291
[35] Zamfirescu, C.; Zamfirescu, T., Hamiltonian properties of grid graphs, SIAM J. Discrete Math., 5, 4, 564-570, (1992) · Zbl 0770.05073
[36] Zhang, Z.; Li, H., Algorithms for long paths in graphs, Theor. Comput. Sci., 377, 1-3, 25-34, (2007) · Zbl 1117.68057
[37] Zhang, W. Q.; Liu, Y. J., Approximating the longest paths in grid graphs, Theor. 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.