scientific article; zbMATH DE number 3882232
From MaRDI portal
Publication:3216469
[For the entire collection see Zbl 0527.00031.] Known approximation algorithms for the traveling salesman problem in the plane produce tours which can still contain intersecting edges. We prove that the common procedure to remove all intersections from a tour without increasing its length, is guaranteed to terminate within polynomially many steps.
Recommendations
- A simple and quick approximation algorithm for traveling salesman problem in the plane
- TRAVELING SALESMAN PROBLEM OF SEGMENTS
- The traveling salesmanpProblem for lines in the plane
- The traveling salesman problem with few inner points
- A polynomial algorithm for a constrained traveling salesman problem
Cited in
(18)- Generating random polygons with given vertices
- Connecting polygonizations via stretches and twangs
- Fréchet distance between two point sets
- Bounded-angle minimum spanning trees
- A new algorithm for embedding plane graphs at fixed vertex locations
- Flip distance to some plane configurations
- Use of simple polygonal chains in generating random simple polygons
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Crossing-free perfect matchings in wheel point sets
- 2-opt moves and flips for area-optimal polygonizations
- Flip distance to some plane configurations
- Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
- The Number of Flips Required to Obtain Non-crossing Convex Cycles
- Untangled monotonic chains and adaptive range search
- The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
- Approximation ineffectiveness of a tour-untangling heuristic
- Performance of efficient variants of the 2-opt heuristic for the traveling salesperson problem
- On triconnected and cubic plane graphs on given point sets
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3216469)