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

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri | Asghar Asgharian-Sardroud

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=84922
Date :  2012/02/01
Publish in :    Discrete Applied Mathematics
DOI :  https://doi.org/10.1016/j.dam.2011.08.010
Link :  https://www.sciencedirect.com/science/article/pii/S0166218X11003088
Keywords :linear-time, longest, rectangular, graphs

Abstract :

---

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.