Hamiltonian Paths in Two Classes of Grid Graphs

2011/07/09 by Fatemeh Keshavarz-Kohjerdi, Keshavarz-Kohjerdi, Fatemeh, Alireza Bagheri +1
Computer Science · #05C45 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #msc:05C45

paper · pdf · doi:10.48550/arxiv.1107.1780

11pages, 7figures

arxiv created 2011/07/09 · arxiv updated 2011/07/12

Abstract

In this paper, we give the necessary and sufficient conditions for the existence of Hamiltonian paths in L-alphabet and C-alphabet grid graphs. We also present a linear-time algorithm for finding Hamiltonian paths in these graphs.

Related

• Hamiltonian Paths in C-shaped Grid Graphs
• 2-Trees: Structural Insights and the study of Hamiltonian Paths
• Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs
• Graphs with Many Hamiltonian Paths
• Hamiltonian paths on directed grids