Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections

David Gamarnik, David Goldberg

We derive new results for the performance of a simple greedy algorithm for finding large independent sets and matchings in constant degree regular graphs. We show that for $r$-regu…