A partitioning algorithm for minimum weighted Euclidean matching

DOI10.1016/0020-0190(84)90024-3zbMath0539.68063OpenAlexW1991462609WikidataQ56324183 ScholiaQ56324183MaRDI QIDQ794175

Martin Dyer, Alan M. Frieze

Publication date: 1984

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90024-3

zbMATH Keywords

probabilistic analysis of algorithmsminimal weighted Euclidean matching

Mathematics Subject Classification ID

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

Related Items

On the Euclidean assignment problem, Quantizers ad the worst case Euclidean traveling salesman problem, Smoothed analysis of partitioning algorithms for Euclidean functionals, Heuristic methods and applications: A categorized survey, Partitioning heuristics for two geometric maximization problems

Cites Work

• Worst case bounds for the Euclidean matching problem
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• On a Greedy Heuristic for Complete Matching
• A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices