Randomized greedy matching. II

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 vertices u, v from G along with any vertices that become isolated. Our main result is that t...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 1995-01, Vol.6 (1), p.55-73
Main Authors: Aronson, Jonathan, Dyer, Martin, Frieze, Alan, Suen, Stephen
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.3240060107