Hamiltonian paths in L-shaped grid graphs

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=84948
Date :  2016/03/28
Publish in :    Theoretical Computer Science

Link :  https://www.sciencedirect.com/science/article/pii/S0304397516000487
Keywords :Hamiltonian, L-shaped, graphs

Abstract :

---

Grid graphs are subgraphs of the infinite 2-dimensional integer grid. The Hamiltonian path problem for general grid graphs is a well-known NP-complete problem. In this paper, we present necessary and sufficient conditions for the existence of a Hamiltonian path between two given vertices in L-shaped grid graphs. We also show that a Hamiltonian path between two given vertices of a L-shaped grid graph can be computed in linear time.