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

boundforestsgreedy algorithmmatchingplanar graphssparse graphs

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(24)

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

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)