07-04
Complexity of the Hamiltonian Cycle Problem in Triangular Grid Graphs
by Gordon, V.S.; Orlovich, Y.L.; Werner, F.
Preprint series: 07-04, Preprints
The paper is published: Discrete Mathematics, Vol. 308, No. 24, 2008, 6166 - 6188 as a part of the paper with the title `Hamiltonian properties of triangular grid graphs\'.
- MSC:
- 05C38 Paths and cycles, See also {90B10}
- 05C45 Eulerian and Hamiltonian graphs
- 68Q25 Analysis of algorithms and problem complexity
Abstract: A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. We show that the problem Hamiltonian Cycle is NP-complete for triangular grid graphs, while a hamiltonian cycle in a connected, locally connected triangular grid graph can be found in polynomial time.
Keywords: Hamiltonian cyle problem, Triangular grid graphs, Complexity
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.