Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs

DOI10.1017/S0963548300001474zbMath0831.90116OpenAlexW2060269923MaRDI QIDQ4844489

Stephen Suen, Andrew John Radcliffe, Alan M. Frieze

Publication date: 27 August 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300001474

zbMATH Keywords

random cubic graphsgreedy matching algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80)

Related Items (3)

Greedy Matching in Bipartite Random Graphs ⋮ Finding maximum matchings in random regular graphs in linear expected time ⋮ Greedy matching: guarantees and limitations

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• A Fast Perfect-Matching Algorithm in Random Graphs
• Randomized greedy matching

This page was built for publication: Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs