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

DOI10.1016/0020-0190(94)00071-9zbMath0806.90121OpenAlexW2003687734MaRDI QIDQ1332749

Günter Rote, René van Dal, Vladimir G. Deǐneko

Publication date: 5 September 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00071-9

zbMATH Keywords

shortest pathpolynomial time algorithmEuclidean traveling salesmanwell-solvable case

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (14)

An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays ⋮ Novel concave hull-based heuristic algorithm for TSP ⋮ The Convex-hull-and-k-line Travelling Salesman Problem ⋮ The two-convex-polygons TSP: A solvable case ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ Well-solved cases of the 2-peripatetic salesman problem ⋮ Computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane ⋮ Hard to solve instances of the Euclidean traveling salesman problem ⋮ A polynomial algorithm for a constrained traveling salesman problem ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem ⋮ Euclidean TSP on two polygons ⋮ On the integrality ratio of the subtour LP for Euclidean TSP ⋮ Routing heuristics for automated pick and place machines ⋮ Euclidean TSP between two nested convex obstacles

Cites Work

• Geometric applications of a matrix-searching algorithm
• The Euclidean traveling salesman problem is NP-complete
• Efficient special case algorithms for the n-line planar traveling salesman problem
• The n-line traveling salesman problem
• On Some Properties of Shortest Hamiltonian Circuits
• The Traveling-Salesman Problem

This page was built for publication: The convex-hull-and-line traveling salesman problem: A solvable case