scientific article; zbMATH DE number 3882232

MaRDI QIDQ3216469zbMATH OpenFDO

Authors J. Van Leeuwen, Anneke A. Schoone

Publication date 1982

zbMATH Keywords

approximation algorithmsintersecting edgesintersection elimination algorithmpolynomial timetraveling salesman

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 2080248
• 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)