ODD MINIMUM CUT SETS AND b-MATCHINGS REVISITED

被引：36

作者：

Letchford, Adam N. ^{[1
]}

Reinelt, Gerhard ^{[2
]}

Theis, Dirk Oliver ^{[3
]}

机构：

[1] Univ Lancaster, Dept Management Sci, Lancaster LA1 4YW, England

[2] Univ Heidelberg, Inst Comp Sci, Heidelberg, Germany

[3] Univ Libre Bruxelles, Dept Math, Combinatoire & Theorie Grp, Serv Geometri, Brussels, Belgium

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2008年 / 22卷 / 04期

基金：

英国工程与自然科学研究理事会;

关键词：

matching; polyhedra; separation;

D O I：

10.1137/060664793

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The famous Padberg-Rao separation algorithm for b-matching polyhedra can be implemented to run in O(vertical bar V vertical bar(2) vertical bar E vertical bar log(vertical bar V vertical bar(2)/vertical bar E vertical bar)) time in the uncapacitated case, and in O(vertical bar V vertical bar vertical bar E vertical bar(2) log (vertical bar V vertical bar(2)/vertical bar E vertical bar)) time in the capacitated case. We give a new and simple algorithm for the capacitated case which can be implemented to run in O(vertical bar V vertical bar(2)vertical bar E vertical bar log(vertical bar V vertical bar(2)/vertical bar E vertical bar)) time.

引用

页码：1480 / 1487

页数：8

共 18 条

[1] The capacitated arc routing problem: Valid inequalities and facets
Belenguer, JM
Benavent, E
[J]. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 1998, 10 (02) : 165 - 187
[2] {0,1/2}-Chvatal-Gomory cuts
Caprara, A
Fischetti, M
[J]. MATHEMATICAL PROGRAMMING, 1996, 74 (03) : 221 - 235
[3] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES
EDMONDS, J
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 125 - +
[4] A branch-and-cut algorithm for the Undirected Rural Postman Problem
Ghiani, G
Laporte, G
[J]. MATHEMATICAL PROGRAMMING, 2000, 87 (03) : 467 - 481
[5] A NEW APPROACH TO THE MAXIMUM-FLOW PROBLEM
GOLDBERG, AV
TARJAN, RE
[J]. JOURNAL OF THE ACM, 1988, 35 (04) : 921 - 940
[6] MULTI-TERMINAL NETWORK FLOWS
GOMORY, RE
HU, TC
[J]. JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04): : 551 - 570
[7] COMPUTATIONAL RESULTS WITH A CUTTING PLANE ALGORITHM FOR DESIGNING COMMUNICATION-NETWORKS WITH LOW-CONNECTIVITY CONSTRAINTS
GROTSCHEL, M
MONMA, CL
STOER, M
[J]. OPERATIONS RESEARCH, 1992, 40 (02) : 309 - 330
[8] SYMMETRIC TRAVELING SALESMAN PROBLEM .2. LIFTING THEOREMS AND FACETS
GROTSCHEL, M
PADBERG, MW
[J]. MATHEMATICAL PROGRAMMING, 1979, 16 (03) : 281 - 302
[9] A CUTTING PLANE ALGORITHM FOR MINIMUM PERFECT 2-MATCHINGS
GROTSCHEL, M
HOLLAND, O
[J]. COMPUTING, 1987, 39 (04) : 327 - 344
[10] SYMMETRIC TRAVELING SALESMAN PROBLEM .1. INEQUALITIES
GROTSCHEL, M
PADBERG, MW
[J]. MATHEMATICAL PROGRAMMING, 1979, 16 (03) : 265 - 280

← 1 2 →