The average performance of the greedy matching algorithm

DOI10.1214/aoap/1177005436zbMath0779.60009OpenAlexW2149720761MaRDI QIDQ687707

Martin Dyer, Boris G. Pittel, Alan M. Frieze

Publication date: 28 October 1993

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1177005436

zbMATH Keywords

asymptotic normalitycentral limit theoremrandom treesgreedy matching algorithms on sparse random graphs

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (7)

Surprising identities for the greedy independent set on Cayley trees ⋮ \(q\)-distributions and Markov processes ⋮ Greedy Matching in Bipartite Random Graphs ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ Finite size scaling for the core of large random hypergraphs ⋮ Normal convergence problem? Two moments and a recurrence may be the clues ⋮ The matching process and independent process in random regular graphs and hypergraphs

This page was built for publication: The average performance of the greedy matching algorithm