Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

被引：14

作者：

Chebolu, Prasad ^{[1
]}

Frieze, Alan ^{[1
]}

Melsted, Pall ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

JOURNAL OF THE ACM | 2010年 / 57卷 / 04期

基金：

美国国家科学基金会;

关键词：

Algorithms; Theory; Random graphs; matching; ALGORITHMS;

D O I：

10.1145/1734213.1734218

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

引用

页数：27

共 10 条

[1]

[Anonymous], 1980, EUR J COMBIN

[2]

[Anonymous], P 22 ANN IEEE S FDN

[3]

Aronson J, 1998, RANDOM STRUCT ALGOR, V12, P111, DOI 10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO

[4]

2-#

[5] Matching algorithms are fast in sparse random graphs [J].

Bast, H ;

Mehlhorn, K ;

Schäfer, G ;

Tamaki, H .

THEORY OF COMPUTING SYSTEMS, 2006, 39 (01) :3-14

[6] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03) :449-&

[7]

FRIEZE AM, 2004, TRENDS MATH, V17, P95

[8]

MCKAY BD, 1985, ARS COMBINATORIA, V19A, P15

[9]

Micali S., 1980, 21st Annual Symposium on Foundations of Computer Science, P17

[10] AVERAGE-CASE ANALYSIS OF ALGORITHMS FOR MATCHINGS AND RELATED PROBLEMS [J].

MOTWANI, R .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1994, 41 (06) :1329-1356

← 1 →