A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random   Graphs
  We propose a new greedy algorithm for the maximum cardinality matching problem. We give experimental evidence that this algorithm is likely to find a maximum matching in random graphs with constant expected degree c>0, independent of the value of c. This is contrary to the behavior of commonly used greedy matching heuristics which are known to have some range of c where they probably fail to compute a maximum matching. 
Martin Dietzfelbinger and Hendrik Peilke and Michael Rink
cs.DS