Randomized greedy matching

DOI10.1002/rsa.3240020104zbMath0763.05080OpenAlexW1970411956WikidataQ56324116 ScholiaQ56324116MaRDI QIDQ3970901

Martin Dyer, Alan M. Frieze

Publication date: 25 June 1992

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240020104

zbMATH Keywords

matchinggreedy algorithmplanar graphsboundsparse graphsforests

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Greedy Matching in Bipartite Random Graphs ⋮ Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming ⋮ Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs ⋮ Randomized greedy matching. II ⋮ Greedy matching: guarantees and limitations ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Excuse me! or the courteous theatregoers' problem ⋮ The matching process and independent process in random regular graphs and hypergraphs

This page was built for publication: Randomized greedy matching