scientific article; zbMATH DE number 1033855

DOI10.1002/(SICI)1098-2418(199705)10:3%3C353::AID-RSA5%3E3.0.CO;2-VMaRDI QIDQ4344227zbMATH OpenFDO

Authors Z. Miller, Dan Pritikin

Publication date 1 June 1998

Full work available at URL https://doi.org/10.1002/(SICI)1098-2418(199705)10:3%3C353::AID-RSA5%3E3.0.CO;2-V

zbMATH Keywords

matchingrandomized greedy algorithmweights

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Randomized greedy matching. II
• Towards a better understanding of randomized greedy matching
• scientific article; zbMATH DE number 1003244
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
• Greedy matching in bipartite random graphs
• On randomized matching mechanisms
• Random matching problems on the complete graph

Cited in

(17)

• Greedy matching in Young's lattice
• On randomized matching mechanisms
• On a conjecture by Gale about one-sided matching problems
• Lazy Gale-Shapley for many-to-one matching with partial information
• Greedy Matching on the Line
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Randomized greedy matching
• Randomized greedy matching. II
• scientific article; zbMATH DE number 1003244 (Why is no real title available?)
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• scientific article; zbMATH DE number 6850371 (Why is no real title available?)
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Greedy matching: guarantees and limitations
• A natural barrier in random greedy hypergraph matching
• The average size of maximal matchings in graphs

This page was built for publication:

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