Shahed University
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.
Authors' Home page
Fatemeh Keshavarz-Kohjerdi