Hamiltonian Paths in Some Classes of Grid Graphs
Joint Authors
Keshavarz-Kohjerdi, Fatemeh
Bagheri, Alireza
Source
Journal of Applied Mathematics
Issue
Vol. 2012, Issue 2012 (31 Dec. 2012), pp.1-17, 17 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2012-04-26
Country of Publication
Egypt
No. of Pages
17
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Keshavarz-Kohjerdi, Fatemeh& Bagheri, Alireza. 2012. Hamiltonian Paths in Some Classes of Grid Graphs. Journal of Applied Mathematics،Vol. 2012, no. 2012, pp.1-17.
https://search.emarefa.net/detail/BIM-993286
Modern Language Association (MLA)
Keshavarz-Kohjerdi, Fatemeh& Bagheri, Alireza. Hamiltonian Paths in Some Classes of Grid Graphs. Journal of Applied Mathematics No. 2012 (2012), pp.1-17.
https://search.emarefa.net/detail/BIM-993286
American Medical Association (AMA)
Keshavarz-Kohjerdi, Fatemeh& Bagheri, Alireza. Hamiltonian Paths in Some Classes of Grid Graphs. Journal of Applied Mathematics. 2012. Vol. 2012, no. 2012, pp.1-17.
https://search.emarefa.net/detail/BIM-993286
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-993286