Hamiltonian paths in some classes of grid graphs (Q442933): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q58905946, #quickstatements; #temporary_batch_1704712062442 |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 04:07, 30 January 2024
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
