A linear-time algorithm for the longest path problem in rectangular grid graphs

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.

► 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.
► We give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph.
► It is shown that any longest path between any two vertices of a rectangular grid graph excludes at most two vertices of the graph.