A polynomial algorithm for a constrained traveling salesman problem

DOI10.1002/NET.1025MaRDI QIDQ2748381zbMATH OpenOpenAlexDBLPWikidataFDO

Authors J. Hyam Rubinstein, D. A. Thomas, Nicholas Wormald

Publication date 14 October 2001

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.1025

zbMATH Keywords

Euclidean traveling salesman problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Recommendations

• The traveling salesman problem with few inner points
• scientific article; zbMATH DE number 34438
• The two-convex-polygons TSP: A solvable case
• TRAVELING SALESMAN PROBLEM OF SEGMENTS
• scientific article; zbMATH DE number 4108531

Cites work

• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• Efficient special case algorithms for the n-line planar traveling salesman problem
• Steiner Trees for Terminals Constrained to Curves
• The Convex-hull-and-k-line Travelling Salesman Problem
• The convex-hull-and-line traveling salesman problem: A solvable case
• The n-line traveling salesman problem

Cited in

(12)

• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• scientific article; zbMATH DE number 3882232 (Why is no real title available?)
• Algorithmic aspects of pyramidal tours with restricted jump-backs
• The \(x\)-and-\(y\)-axes travelling salesman problem
• scientific article; zbMATH DE number 4108531 (Why is no real title available?)
• On the generation of metric TSP instances with a large integrality gap by branch-and-cut
• scientific article; zbMATH DE number 4083394 (Why is no real title available?)
• Hard to solve instances of the Euclidean traveling salesman problem
• scientific article; zbMATH DE number 5819786 (Why is no real title available?)
• A strongly polynomial algorithm for the transportation problem
• Traveling salesman-based curve reconstruction in polynomial time
• scientific article; zbMATH DE number 6007907 (Why is no real title available?)

This page was built for publication: A polynomial algorithm for a constrained traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2748381)