##
Günter Rote:

#
Two solvable cases of the traveling salesman problem

*Ph. D. thesis, Technische Universität Graz, May 1988, 55 pages.
(Supervisor: Prof. Dr. R. E.
Burkard).
*
This thesis
contains the
paper The *N*-line
traveling salesman problem
and an extension of the paper
Testing
the necklace condition for shortest tours and optimal factors in the
plane, written jointly with Herbert Edelsbrunner and Emo Welzl.
The improvement of the latter part has not been published elsewhere.

### Abstract

In the Euclidean traveling salesman problem, a set of points in the
plane is given,
and we look for a shortest closed curve through these lines (a "tour").
We treat two special cases of this problem which are solvable in
polynomial time.
The first solvable case is the
*N-line traveling salesman problem*, where the points lie on a
small number (*N*) of
parallel lines.
Such problems arise for example in the fabrication of printed circuit
boards,
where the distance traveled by a laser which drills holes in certain
places of
the board should be minimized.
By a dynamic programming algorithm, we can solve
the *N*-line traveling salesman problem for *n* points in
time *n*^{N},
for fixed *N*, i. e.,
in polynomial time. This extends a result of Cutler (1980) for
3 lines.
The parallelity condition can be relaxed to point sets which
lie on *N* "almost parallel" line segments.
The other solvable case concerns the *necklace
condition*: A 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*(*n*^{3/2})
time
whether a *given* tour is a necklace tour,
improving an algorithm of Edelsbrunner,
Rote, and Welzl
(1988) which takes *O*(*n*^{2})
time. It is based on solving a system of
linear inequalities by the *generalized nested dissection*
procedure of
Lipton,
Rose, and Tarjan (1979). We describe how this method can be implemented
with only linear storage.
We give another algorithm which tests in *O*(*n*^{2} 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 also compute radii for the disks realizing the necklace
tour.