A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs

Martin Dietzfelbinger, Hendrik Peilke, Michael Rink

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 gra…