Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time.

Prasad Chebolu Alan M. Frieze Páll Melsted

Published in: ICALP (1) (2008)

Keyphrases

maximum matching
random graphs
bipartite graph
graph theoretic
stable set
active learning
optimal solution
undirected graph
small world