Randomized greedy matching
作者:
Martin Dyer,
Alan Frieze,
期刊:
Random Structures&Algorithms
(WILEY Available online 1991)
卷期:
Volume 2,
issue 1
页码: 29-45
ISSN:1042-9832
年代: 1991
DOI:10.1002/rsa.3240020104
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractWe consider a randomized version of the greedy algorithm for finding a large matching in a graph. We assume that the next edge is always randomly chosen from those remaining. We analyze the performance of this algorithm when the input graph is fixed. We show that there are graphs for which this Randomized Greedy Algorithm(RGA)usually only obtains a matching close in size to that guaranteed by worst‐case analysis (i.e., half the size of the maximum). For some classes of sparse graphs (e.g., planar graphs and forests) we show that theRGAperforms significantly better than the worst‐case. Our main theorem concerns forests. We prove that the ratio to maximum here is at least 0.7690…, and that this bound is
点击下载:
PDF
(536KB)
返 回