The Weighted Matching Approach to Maximum Cardinality Matching

被引：15

作者：

Gabow, Harold N. ^{[1
]}

机构：

[1] Univ Colorado, Dept Comp Sci, Boulder, CO 80309 USA

来源：

FUNDAMENTA INFORMATICAE | 2017年 / 154卷 / 1-4期

关键词：

D O I：

10.3233/FI-2017-1555

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Several papers have achieved time O (root nm) for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds' algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time O (root nm).

引用

页码：109 / 130

页数：22

共 13 条

[1]

[Anonymous], 2001, Combinatorial optimization: networks and matroids

[2]

Cook W., 1998, COMBINATORIAL OPTIMI

[3] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[4]

GABOW HN, 1991, J ACM, V38, P815, DOI 10.1145/115234.115366

[5] A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION [J].

GABOW, HN ;

TARJAN, RE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :209-221

[6] Maximum skew-symmetric flows and matchings [J].

Goldberg, AV ;

Karzanov, AV .

MATHEMATICAL PROGRAMMING, 2004, 100 (03) :537-568

[7]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019

[8]

Karzanov AV, 1976, FINDING MAXIMUM FLOW, V5, P81

[9]

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

[10]

Schrijver A, 2003, COMBINATORIAL OPTIMI, VA

← 1 2 →