Hamiltonian Paths in Some Classes of Grid Graphs

Fatemeh Keshavarz-Kohjerdi; Alireza Bagheri

doi:10.1155/2012/475087

Journal of Applied Mathematics (Jan 2012)

Hamiltonian Paths in Some Classes of Grid Graphs

Fatemeh Keshavarz-Kohjerdi,
Alireza Bagheri

Affiliations

Fatemeh Keshavarz-Kohjerdi: Department of Computer Engineering, Islamic Azad University, North Tehran Branch, Tehran, Iran
Alireza Bagheri: Department of Computer Engineering and IT, Amirkabir University of Technology, Hafez Avenue, Tehran, Iran

DOI: https://doi.org/10.1155/2012/475087
Journal volume & issue: Vol. 2012

Abstract

Read online

The Hamiltonian path problem for general grid graphs is known to be NP-complete. In this paper, we give necessary and sufficient conditions for the existence of Hamiltonian paths in L-alphabet, C-alphabet, F-alphabet, and E-alphabet grid graphs. We also present linear-time algorithms for finding Hamiltonian paths in these graphs.

Published in Journal of Applied Mathematics

ISSN: 1110-757X (Print); 1687-0042 (Online)
Publisher: Wiley
Country of publisher: United Kingdom
LCC subjects: Science: Mathematics
Website: https://onlinelibrary.wiley.com/journal/4185

About the journal