Shahed University

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

Date :  2017/08/22
Publish in :    Theoretical Computer Science

Link :
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.