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

DOI10.1016/0020-0190(96)00125-1zbMath0900.68326OpenAlexW2101116363MaRDI QIDQ1350909

Vladimir G. Deǐneko, Gerhard J. Woeginger

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00125-1

zbMATH Keywords

Combinatorial optimizationPolynomial algorithmCombinatorial problemsTravelling salesman problem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (5)

Novel concave hull-based heuristic algorithm for TSP ⋮ A polynomial algorithm for a constrained traveling salesman problem ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem ⋮ Exact and heuristic algorithms for routing AGV on path with precedence constraints ⋮ The traveling salesman problem with few inner points

Cites Work

• Unnamed Item
• Unnamed Item
• The Euclidean traveling salesman problem is NP-complete
• The convex-hull-and-line traveling salesman problem: A solvable case
• Efficient special case algorithms for the n-line planar traveling salesman problem
• The n-line traveling salesman problem
• The Traveling-Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: The Convex-hull-and-k-line Travelling Salesman Problem