A linear-time algorithm for the longest path problem in rectangular grid graphs |
| |
| Authors: | Fatemeh Keshavarz-Kohjerdi Alireza Bagheri |
| |
| Institution: | a Department of Computer Engineering, Islamic Azad University, North Tehran Branch, Tehran, Iranb Department of Computer Engineering & IT, Amirkabir University of Technology, Tehran, Iran |
| |
| 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. |
| |
| Keywords: | Hamiltonian path Hamiltonian cycle Grid graph Longest path Rectangular grid graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
