AN O(EVLOGV) ALGORITHM FOR FINDING A MAXIMAL WEIGHTED MATCHING IN GENERAL GRAPHS

被引：83

作者：

GALIL, Z

MICALI, S

GABOW, H

机构：

[1] COLUMBIA UNIV,DEPT COMP SCI,NEW YORK,NY 10027

[2] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

[3] UNIV COLORADO,BOULDER,CO 80309

来源：

关键词：

D O I：

10.1137/0215009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：120 / 130

页数：11

共 11 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

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

[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 H. N., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P347, DOI 10.1109/SFCS.1984.715935

[5]

Gabow H. N., 1974, THESIS STANFORD U ST

[6] AN O(EVLOG2V) ALGORITHM FOR THE MAXIMAL FLOW PROBLEM [J].

GALIL, Z ;

NAAMAD, A .

[7]

GALIL Z, 1983, EFFICIENT ALGORITHMS

[8]

Karzanov A. V, 1974, SOV MATH DOKL, V15, P434

[9]

Lawler E.L., 1976, COMBINATORIAL OPTIMI

[10]

SLEATOR D, 1980, THESIS STANFORD U ST