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.)


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).

other papers about this subject