A linear-time algorithm for finding Hamiltonian (s, t)-paths in odd-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=84947
Date :  2017/02/23
Publish in :    The Journal of Supercomputing
DOI :  https://doi.org/10.1007/s11227-017-1984-z
Link :  https://www.springerprofessional.de/en/a-linear-time-algorithm-for-finding-hamiltonian-s-t-paths-in-odd/12091452
Keywords :linear-time, Hamiltonian, rectangular, graphs, rectangular

Abstract :

---

A grid graph Gg is a finite vertex-induced subgraph of the two-dimensional integer grid G∞. A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.