A linear-time algorithm for the longest path problem in rectangular grid graphs. (English) Zbl 1237.05115

Summary: The longest path problem is a well-known NP-hard problem and so far it has been solved polynomially only for a few classes of graphs. In this paper, we give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph.


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


[1] Björklund, A.; Husfeldt, T., Finding a path of superlogarithmic length, SIAM J. comput., 32, 6, 1395-1402, (2003) · Zbl 1041.68066
[2] 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, Inform. process. lett., 81, 2, 93-96, (2002) · Zbl 1032.68671
[3] Chen, S.D.; Shen, H.; Topor, R., An efficient algorithm for constructing Hamiltonian paths in meshes, J. parallel comput., 28, 9, 1293-1305, (2002) · Zbl 0999.68253
[4] Diestel, R., Graph theory, (2000), Springer New York · Zbl 0945.05002
[5] Feder, T.; Motwani, R., Finding large cycles in Hamiltonian graphs, (), 166-175 · Zbl 1297.05140
[6] Gabow, H.N., Finding paths and cycles of superpolylogarithmic length, (), 407-416 · Zbl 1192.68361
[7] Gabow, H.N.; Nie, S., Finding long paths, cycles and circuits, (), 752-763 · Zbl 1183.05078
[8] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[9] Gutin, G., Finding a longest path in a complete multipartite digraph, SIAM J. discrete math., 6, 2, 270-273, (1993) · Zbl 0773.05071
[10] Itai, A.; Papadimitriou, C.; Szwarcfiter, J., Hamiltonian paths in grid graphs, SIAM J. comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[11] 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
[12] W. Lenhart, C. Umans, Hamiltonian cycles in solid grid graphs, in: Proc. 38th Annual Symposium on Foundations of Computer Science, FOCS’97, 1997, pp. 496-505.
[13] Ioannidou, K.; Mertzios, G.B.; Nikolopoulos, S., The longest path problem is polynomial on interval graphs, (), 403-414 · Zbl 1250.68128
[14] F. Luccio, C. Mugnia, Hamiltonian paths on a rectangular chessboard, in: Proc. 16th Annual Allerton Conference, 1978, pp. 161-173.
[15] G.B. Mertzios, D.G. Corneil, A simple polynomial algorithm for the longest path problem on cocomparability graphs, in: Proc. of CoRR, 2010.
[16] Uehara, R.; Uno, Y., On computing longest paths in small graph classes, Internat. J. found. comput. sci., 18, 5, 911-930, (2007) · Zbl 1202.68291
[17] Zhang, Z.; Li, H., Algorithms for long paths in graphs, Theoret. comput. sci., 377, 1-3, 25-34, (2007) · Zbl 1117.68057
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.