On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
From MaRDI portal
Publication:6567757
DOI10.1007/3-540-62034-6_38zbMATH Open1541.68154MaRDI QIDQ6567757FDOQ6567757
Authors: Gautam Das, Sanjiv Kapoor, Michiel Smid 
Publication date: 5 July 2024
Recommendations
- On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
- 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 1559518
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Euclidean traveling salesman problem is NP-complete
- Euclidean minimum spanning trees and bichromatic closest pairs
- Title not available (Why is that?)
- Minimum Spanning Trees in k-Dimensional Space
- CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
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 Q6567757)
