On a Greedy Heuristic for Complete Matching

DOI10.1137/0210050zbMath0468.68072OpenAlexW1984735486MaRDI QIDQ3922185

Edward M. Reingold, Robert Endre Tarjan

Publication date: 1981

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0210050

zbMATH Keywords

analysis of algorithmsgraph algorithmsdrawing graphs on a mechanical plotter

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

Recurrence relations based on minimization and maximization, On the existence of weak greedy matching heuristics, New primal and dual matching heuristics, The Price of Matching with Metric Preferences, A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line, Approximation algorithms for weighted matching, Linear-Time Approximation for Maximum Weight Matching, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, Probabilistic analysis of optimization problems on generalized random shortest path metrics, A \(o(n)\)-competitive deterministic algorithm for online matching on a line, Probabilistic analysis of optimization problems on sparse random shortest path metrics, An asymptotic theory for recurrence relations based on minimization and maximization., Worst case bounds for the Euclidean matching problem, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane, Greedy matching on a grid, A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching, Random shortest paths: non-Euclidean instances for metric optimization problems, The ring of \(k\)-regular sequences, Unnamed Item, Deterministic min-cost matching with delays, A genetic-based framework for solving (multi-criteria) weighted matching problems., Heuristic methods and applications: A categorized survey, Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching, A partitioning algorithm for minimum weighted Euclidean matching, Fast and Simple Algorithms for Weighted Perfect Matching, Some recent results in the analysis of greedy algorithms for assignment problems, A lower bound to the complexity of Euclidean and rectilinear matching algorithms