Hamiltonian paths in some classes of grid graphs (Q442933)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hamiltonian paths in some classes of grid graphs |
scientific article |
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
