On a Greedy Heuristic for Complete Matching

DOI10.1137/0210050MaRDI QIDQ3922185zbMATH OpenOpenAlexFDO

Authors Edward M. Reingold, Robert E. 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 algorithmsdrawing graphs on a mechanical plottergraph algorithms

Mathematics Subject Classification ID

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

Cited in

(28)

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

This page was built for publication: On a Greedy Heuristic for Complete Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922185)