Premium
Randomized greedy matching. II
Author(s) -
Aronson Jonathan,
Dyer Martin,
Frieze Alan,
Suen Stephen
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060107
Subject(s) - combinatorics , matching (statistics) , mathematics , vertex (graph theory) , randomized algorithm , greedy algorithm , constant (computer programming) , graph , random graph , discrete mathematics , algorithm , computer science , statistics , programming language
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.