Randomized greedy matching

DOI10.1002/RSA.3240020104MaRDI QIDQ3970901zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dyer, Alan 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 algorithmsparse graphsboundforestsplanar graphs

Mathematics Subject Classification ID

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

Recommendations

• Randomized greedy matching. II
• scientific article; zbMATH DE number 1003244
• scientific article; zbMATH DE number 1033855

Cited in

(21)

• Erratum to: ``Greedy matching: guarantees and limitations
• On randomized matching mechanisms
• Excuse me! or the courteous theatregoers' problem
• Two faces of greedy leaf removal procedure on graphs
• Ranking on arbitrary graphs: rematch via continuous linear programming
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Greedy Matching on the Line
• Randomized greedy matching. II
• Greedy matching in Young's lattice
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• The average size of maximal matchings in graphs
• The average performance of the greedy matching algorithm
• Greedy matching in bipartite random graphs
• scientific article; zbMATH DE number 4099072 (Why is no real title available?)
• scientific article; zbMATH DE number 7650074 (Why is no real title available?)
• Greedy matching: guarantees and limitations
• scientific article; zbMATH DE number 437559 (Why is no real title available?)
• Power balance and apportionment algorithms for the United States Congress
• Greedy maximal independent sets via local limits
• The matching process and independent process in random regular graphs and hypergraphs
• Lazy or eager dynamic matching may not be fast

This page was built for publication: Randomized greedy matching

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