Zurück zu den Preprints des Jahres 2007


2007-04

Complexity of the Hamiltonian Cycle Problem in Triangular Grid Graphs

by Gordon, V.S., Orlovich, Y.L., Werner, F..


Series: 2007-04, Preprints

MSC:
05C38 Paths and cycles
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

This paper was published in:
Discrete Mathematics, Vol. 308, No. 24, 2008, 6166 - 6188 as a part of the paper with the title `Hamiltonian properties of triangular grid graphs'.