Paper Info
Title
Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
Abstract
It is shown that it is an NP-complete problem to determine whether a Delaunay triangulation or an inscribable polyhedron has a Hamiltonian cycle. It is also shown that there exist nondegenerate Delaunay triangulations and simplicial, inscribable polyhedra without 2-factors.
Year
DOI
Venue
1996
10.1016/0166-218X(94)00125-W
Discrete Applied Mathematics
Keywords
DocType
Volume
finding hamiltonian cycle,delaunay triangulations,delaunay triangulation,hamiltonian cycle,np complete problem
Journal
64
Issue
ISSN
Citations 
3
Discrete Applied Mathematics
15
PageRank 
References 
Authors
1.49
13
1
Name
Order
Citations
PageRank
Michael B. Dillencourt149857.58