✦ LIBER ✦

The convex-hull-and-line traveling salesman problem: a solvable case

✍ Scribed by Vladimir G. Deineko; René van Dal; Günter Rote

Book ID: 107766172
Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 649 KB
Volume: 51
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(94)00071-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Convex-hull-and-k-line Travelling Sa

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

✍ Vladimir G. Deĭneko; Gerhard J. Woeginger 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 651 KB

A Solvable Case of the Traveling Salesma

A Solvable Case of the Traveling Salesman Problem

✍ P. C. Gilmore and R. E. Gomory 📂 Article 📅 1964 🏛 National Academy of Sciences 🌐 English ⚖ 182 KB

A solvable case of the traveling salesma

A solvable case of the traveling salesman problem

✍ Eugene L. Lawler 📂 Article 📅 1971 🏛 Springer-Verlag 🌐 English ⚖ 113 KB

A new solvable case of the traveling sal

A new solvable case of the traveling salesman problem

✍ Maciej M. Sysło 📂 Article 📅 1973 🏛 Springer-Verlag 🌐 English ⚖ 64 KB

Worst-case analysis of some convex hull

Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem

✍ A.R Warburton 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 385 KB

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