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

DOI10.1007/PL00009183zbMATH Open0898.68097OpenAlexW2037310342MaRDI QIDQ1386771FDOQ1386771

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

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

zbMATH Keywords

minimum spanning treestraveling salesman tours

Mathematics Subject Classification ID

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

Cited In (12)

• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• Title not available (Why is that?)
• A lower bound for approximating the geometric minimum weight matching
• 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
• Title not available (Why is that?)
• On the bounded-hop MST problem on random Euclidean instances
• Title not available (Why is that?)

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)