RANDOMIZED GREEDY MATCHING .2.

被引：36

作者：

ARONSON, J ^{[1
]}

DYER, M ^{[1
]}

FRIEZE, A ^{[1
]}

SUEN, S ^{[1
]}

机构：

[1] UNIV LEEDS,SCH COMP STUDIES,LEEDS LS2 9JT,W YORKSHIRE,ENGLAND

来源：

RANDOM STRUCTURES & ALGORITHMS | 1995年 / 6卷 / 01期

关键词：

D O I：

10.1002/rsa.3240060107

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 epsilon 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 + epsilon. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs. (C) 1995 John Wiley & Sons, Inc.

引用

页码：55 / 73

页数：19