𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Convex-hull-and-k-line Travelling Salesman Problem

✍ Scribed by Vladimir G. Deĭneko; Gerhard J. Woeginger

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
651 KB
Volume
59
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The n-line traveling salesman problem
The n-line traveling salesman problem
✍ Günter Rote 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 780 KB

The special case of the Euclidean traveling salesman problem, where the n given points lie on a small number (N) of parallel lines in the plane, is solved by a dynamic programming approach in time nN, for fixed N, i.e., in polynomial time. This extends a result of Cutler (1980) for three lines. Such

Efficient special case algorithms for th
Efficient special case algorithms for the n-line planar traveling salesman problem
✍ M. Cutler 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

## Abstract The traveling salesman problem, path, or cycle is NP‐complete. All known exact solutions to this problem are exponential. In the __N‐line planar__ traveling salesman problem the points are on __N__ lines in the plane. In this paper, simple and efficient low‐degree polynomial solutions a