Approximate minimum weight matching on points in k-dimensional space
From MaRDI portal
Publication:1825658
DOI10.1007/BF01553909zbMath0684.68064MaRDI QIDQ1825658
Publication date: 1989
Published in: Algorithmica (Search for Journal in Brave)
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
The Euclidean k-Supplier Problem ⋮ A generalized hypergreedy algorithm for weighted perfect matching ⋮ Fast geometric approximation techniques and geometric embedding problems ⋮ Maximum bipartite matchings with low rank data: locality and perturbation analysis ⋮ A sparse graph almost as good as the complete graph on points in \(k\) dimensions ⋮ Approximation algorithms for lawn mowing and milling
Cites Work
- Unnamed Item
- A survey of heuristics for the weighted matching problem
- Heuristic matching for graphs satisfying the triangle inequality
- Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- Faster scaling algorithms for general graph matching problems
- Maximum matching and a polyhedron with 0,1-vertices
