A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=84949
Date :  2017/08/22
Publish in :    Theoretical Computer Science

Link :  https://www.sciencedirect.com/science/article/pii/S0304397517304759
Keywords :linear-time, Hamiltonian, rectangular, graphs, rectangular

Abstract :

---

The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give the necessary conditions for the existence of a Hamiltonian path between two given vertices in a rectangular grid graph with a rectangular hole; where the size of graph is even. In addition, we show that the Hamiltonian path in these graphs can be computed in linear-time.