Randomized greedy matching. II

DOI10.1002/rsa.3240060107zbMath0812.05046OpenAlexW2110009764WikidataQ56324050 ScholiaQ56324050MaRDI QIDQ4322476

Martin Dyer, Stephen Suen, Jonathan Aronson, Alan M. Frieze

Publication date: 9 May 1995

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

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

zbMATH Keywords

matchingrandomized algorithmhypergraphstreessparse graphsgreedy matching

Mathematics Subject Classification ID

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

Related Items (12)

Greedy Matching in Bipartite Random Graphs ⋮ Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming ⋮ Unnamed Item ⋮ Computing maximum matchings in temporal graphs ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Greedy matching: guarantees and limitations ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ Online Vertex-Weighted Bipartite Matching ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Excuse me! or the courteous theatregoers' problem ⋮ Some recent results in the analysis of greedy algorithms for assignment problems

Cites Work

• Randomized greedy matching
• An Analysis of the Greedy Heuristic for Independence Systems

This page was built for publication: Randomized greedy matching. II