Heuristic matching for graphs satisfying the triangle inequality

DOI10.1016/0196-6774(84)90024-5zbMath0543.68047OpenAlexW2016406297MaRDI QIDQ3332259

David Alan Plaisted

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90024-5

zbMATH Keywords

factor of two methodhyper-greedy methodmatching heuristics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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, A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching, A generalized hypergreedy algorithm for weighted perfect matching, Heuristic methods and applications: A categorized survey, Approximate minimum weight matching on points in k-dimensional space, A greedy heuristic for a minimum-weight forest problem, A lower bound to the complexity of Euclidean and rectilinear matching algorithms