Hamiltonian paths in some classes of grid graphs (Q442933)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Hamiltonian paths in some classes of grid graphs |
scientific article; zbMATH DE number 6063400
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hamiltonian paths in some classes of grid graphs |
scientific article; zbMATH DE number 6063400 |
Statements
Hamiltonian paths in some classes of grid graphs (English)
0 references
6 August 2012
0 references
Summary: 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.
0 references
linear-time algorithms
0 references
\(L\)-alphabet
0 references
\(C\)-alphabet,
0 references
\(F\)-alphabet
0 references
\(E\)-alphabet
0 references
0.9591383
0 references
0 references
0.92975134
0 references
0.9258347
0 references
0 references
0 references
