Herbert Edelsbrunner, Günter Rote, and Emo Welzl:
Testing the necklace condition for shortest tours and optimal factors in
the plane
1. Theoretical Computer Science 66 (1989), 157-180, (MR #90i:90042).
2. In: "Automata, Languages, and Programming". Proceedings of the
14th International Colloquium on Automata, Languages, and Programming (ICALP),
Karlsruhe, Juli 1987. Editor: T. Ottmann. Lecture Notes in Computer Science
266, Springer-Verlag, 1987, pp. 364-375, (Zbl 636.68042, MR #88k:90065).
(This is a shortened and slightly modified version.)
Abstract
A traveling salesman tour is a necklace tour if we can draw
disks with the given points as centers such that two
disks intersect if and only if the corresponding points are adjacent on the
tour.
If a necklace tour exists, it is the unique optimal tour.
We give an algorithm which tests in
O(n2) time
whether a given tour is a necklace tour.
We give another algorithm which tests
in O(n2 log n) time and linear
space whether a necklace tour exists
for a given point set, by
transforming
the problem to a fractional 2-factor problem on a sparse bipartite graph.
Both algorithms can be generalized to m-factors of
point sets in the plane.
Note. In his dissertation,
Two
solvable cases of the traveling salesman problem, Günter Rote has
improved the
time complexity of the algorithm for testing a given tour to
O(n3/2). The new algorithm is based on solving a system of
linear inequalities by the generalized nested dissection procedure of
Lipton, Rose, and Tarjan (1979).