The Travelling Salesman Problem and Minimum Matching in the Unit Square

DOI10.1137/0212009MaRDI QIDQ3967062zbMATH OpenOpenAlexFDO

Authors Kenneth J. Supowit, Edward M. Reingold, David A. Plaisted

Publication date 1983

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0212009

zbMATH Keywords

analysis of algorithmscomputational geometrygraph algorithmsheuristics

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(15)

• Quantizers ad the worst case Euclidean traveling salesman problem
• Worst-case minimum rectilinear Steiner trees in all dimensions
• Heuristic methods and applications: A categorized survey
• Approximation schemes for node-weighted geometric Steiner tree problems
• A concentration inequality for the facility location problem
• An upper bound for the average length of the euclidean minimum spanning tree
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
• Minimum weight Euclidean (1+)-spanners
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• On a traveling salesman problem for points in the unit cube
• Lower bounds for rectilinear Steiner trees in bounded space
• A partitioning algorithm for minimum weighted Euclidean matching
• Partitioning heuristics for two geometric maximization problems
• The physicist's approach to the travelling salesman problem. II

This page was built for publication: The Travelling Salesman Problem and Minimum Matching in the Unit Square

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