A lower bound for approximating the geometric minimum weight matching

DOI10.1016/S0020-0190(00)00062-4zbMATH Open1338.68260OpenAlexW2028997225MaRDI QIDQ294775FDOQ294775

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• Geometry Helps in Matching
• Title not available (Why is that?)

Cited In (4)

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

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)