Testing the necklace condition for shortest tours and optimal factors in the plane Journal Article


Author(s): Edelsbrunner, Herbert; Rote, Günter; Welzl, Emo
Article Title: Testing the necklace condition for shortest tours and optimal factors in the plane
Affiliation
Abstract: A tour of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour. In this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.
Journal Title: Theoretical Computer Science
Volume: 66
Issue 2
ISSN: 0304-3975
Publisher: Elsevier  
Date Published: 1989-08-01
Start Page: 157
End Page: 180
DOI: 10.1016/0304-3975(89)90133-3
Open access: no