A lower bound for approximating the geometric minimum weight matching

DOI10.1016/S0020-0190(00)00062-4MaRDI QIDQ294775zbMATHOpenAlexFDO

Authors Michiel Smid, Gautam Das

Publication date 16 June 2016

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

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000000624?np=y

zbMATH Keywords

computational geometrylower boundsminimum weight matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Approximate minimum weight matching on points in k-dimensional space
• A lower bound to the complexity of Euclidean and rectilinear matching algorithms
• Geometry Helps in Matching
• An EP Algorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane
• Computing Minimum-Weight Perfect Matchings

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• Geometry Helps in Matching
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees

Cited in

(4)

• A lower bound to the complexity of Euclidean and rectilinear matching algorithms
• An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon
• Inexpensive d‐dimensional matchings
• Approximate minimum weight matching on points in k-dimensional space

This page was built for publication: A lower bound for approximating the geometric minimum weight matching

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