Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane

DOI10.1016/0020-0190(81)90103-4zbMath0459.68037OpenAlexW2041963282MaRDI QIDQ1152226

Kazuo Murota, Masao Iri, Shouichi Matsui

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90103-4

zbMATH Keywords

graphics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Discrete mathematics in relation to computer science (68R99)

Related Items

On the existence of weak greedy matching heuristics, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, Heuristic methods and applications: A categorized survey, Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching

Cites Work

• Unnamed Item
• On a Greedy Heuristic for Complete Matching