RANDOMIZED GREEDY MATCHING .2.

We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V,E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete ver tices u, v from G along with any vertices that become isolated. Our ma in result is that there exists a positive constant epsilon such that t he expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + epsilon. We obtain stronger re sults for sparse graphs and trees and consider extensions to hypergrap hs. (C) 1995 John Wiley & Sons, Inc.