On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees

DOI10.1007/PL00009183MaRDI QIDQ1386771zbMATH OpenOpenAlexFDO

Authors Gautam K. Das, Sanjiv Kapoor, Michiel Smid

Publication date 10 November 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009183

zbMATH Keywords

minimum spanning treestraveling salesman tours

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• scientific article; zbMATH DE number 1163704
• A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
• scientific article; zbMATH DE number 1436136

Cited in

(12)

• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• A lower bound for approximating the geometric minimum weight matching
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Not all insertion methods yield constant approximate tours in the Euclidean plane
• On two geometric problems related to the travelling salesman problem
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• scientific article; zbMATH DE number 1559518 (Why is no real title available?)
• On the bounded-hop MST problem on random Euclidean instances
• scientific article; zbMATH DE number 7526265 (Why is no real title available?)

This page was built for publication: On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees

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