A Fast Perfect-Matching Algorithm in Random Graphs

DOI10.1137/0403006MaRDI QIDQ3360222zbMATH OpenOpenAlexFDO

Authors Olivier Goldschmidt, Dorit S. Hochbaum

Publication date 1990

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0403006

zbMATH Keywords

greedy matching algorithmperfect matchingrandom graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• STACS 2004
• Matching algorithms are fast in sparse random graphs
• Perfect matchings in the semirandom graph process
• A perfect matching algorithm for sparse bipartite graphs
• Efficient random graph matching via degree profiles
• Random matching problems on the complete graph
• Finding maximum matchings in random regular graphs in linear expected time
• Perfect matchings in random intersection graphs
• Efficient algorithms for finding maximum matching in graphs
• Maximum matchings in general graphs through randomization

Cited in

(6)

• An efficient matching algorithm applied in statistical physics
• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• 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
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• A natural barrier in random greedy hypergraph matching

This page was built for publication: A Fast Perfect-Matching Algorithm in Random Graphs

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