A lower bound for approximating the geometric minimum weight matching

DOI10.1016/S0020-0190(00)00062-4zbMath1338.68260OpenAlexW2028997225MaRDI QIDQ294775

Gautam K. Das, Michiel H. M. Smid

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

lower boundscomputational geometryminimum weight matching

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• Geometry Helps in Matching

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