A POLYNOMIAL ALGORITHM FOR B-MATCHINGS - AN ALTERNATIVE APPROACH

被引：67

作者：

ANSTEE, RP ^{[1
]}

机构：

[1] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO N2L 3G1,ONTARIO,CANADA

来源：

INFORMATION PROCESSING LETTERS | 1987年 / 24卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

MATHEMATICAL TECHNIQUES - Graph Theory;

D O I：

10.1016/0020-0190(87)90178-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A b-matching of a given graph G is an assignment of integer weights to the edges of G so that the sum of the weights on the edges incident with a vertex v is at most b//v(b denotes the vectors of b//v's). When b//v equals 1 for all vertices v in G, then b-matchings are the usual matchings. The b-matching problem asks for a b-machine of maximum cost where the edges of G have been assigned costs and the cost of a b-matching is the sum of the weights times the costs. We do not assume G to be bipartite. We present an algorithm for the b-matching problem that is strongly polynomial.

引用

页码：153 / 157

页数：5

共 17 条

[1] AN ALGORITHMIC PROOF OF TUTTES F-FACTOR THEOREM [J].

ANSTEE, RP .

JOURNAL OF ALGORITHMS, 1985, 6 (01) :112-131

[2] DESIGN AND IMPLEMENTATION OF LARGE-SCALE PRIMAL TRANSSHIPMENT ALGORITHMS [J].

BRADLEY, GH ;

BROWN, GG ;

GRAVES, GW .

MANAGEMENT SCIENCE, 1977, 24 (01) :1-34

[3] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

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

[4] 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-+

[5]

EDMONDS J, 1970, COMBINATORIAL STRUCT, P89

[6] SOME PROPERTIES OF GRAPHS WITH MULTIPLE EDGES [J].

FULKERSON, DR ;

HOFFMAN, AJ ;

MCANDREW, MH .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (01) :166-+

[7]

Gabow H. N., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P347, DOI 10.1109/SFCS.1984.715935

[8]

Gabow H. N., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P90, DOI 10.1109/SFCS.1985.3

[9]

GABOW HN, 1983, 15TH P ANN ACM S THE

[10]

Galil Z., 1982, 23rd Annual Symposium on Foundations of Computer Science, P255, DOI 10.1109/SFCS.1982.36

← 1 2 →