Efficient special case algorithms for the n-line planar traveling salesman problem

✍ Scribed by M. Cutler

• Publisher: John Wiley and Sons
• Year: 1980
• Tongue: English
• Weight: 482 KB
• Volume: 10
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230100302

✦ Synopsis

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 are given to some N‐line (N = 2, 3) planar traveling salesman problems using dynamic programming. Such problems arise in practical applications, for example, connecting nets in printed circuits.