Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=169814
Date :  2022/09/11
Publish in :    Applied Mathematics and Computation
DOI :  https://doi.org/https://doi.org/10.1016/j.amc.2022.127513
Link :  https://www.sciencedirect.com/science/article/pii/S0096300322005872
Keywords :Hamiltonian cycle problem,Solid grid graph,Truncated rectangular grid graphs,Linear-time algorithm

Abstract :

---

The Hamiltonian cycle problem is an important problem in graph theory. For solid grid graphs, an O(n4) -time algorithm has been given. In this paper, we solve the problem for a special class of solid grid graphs, i.e. truncated rectangular grid graphs, in linear time.