| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419450 | Discrete Applied Mathematics | 2012 | 8 Pages |
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.
► 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri, Asghar Asgharian-Sardroud,