Finding a maximum matching in a sparse random graph in O ( n ) expected time

DOI10.1145/1734213.1734218zbMath1327.05319OpenAlexW2063911102WikidataQ57401462 ScholiaQ57401462MaRDI QIDQ3578203

Páll Melsted, Prasad Chebolu, Alan M. Frieze

Publication date: 14 July 2010

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1734213.1734218

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three ⋮ On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Finding maximum matchings in random regular graphs in linear expected time ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs ⋮ Unnamed Item

This page was built for publication: Finding a maximum matching in a sparse random graph in O ( n ) expected time