RANDOM PSEUDO-POLYNOMIAL ALGORITHMS FOR EXACT MATROID PROBLEMS

被引：50

作者：

CAMERINI, PM

GALBIATI, G

MAFFIOLI, F

机构：

[1] UNIV SIENA,I-53100 SIENNA,ITALY

[2] UNIV PAVIA,I-27100 PAVIA,ITALY

[3] POLITECN MILAN,I-20133 MILAN,ITALY

来源：

JOURNAL OF ALGORITHMS | 1992年 / 13卷 / 02期

关键词：

D O I：

10.1016/0196-6774(92)90018-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this work we present a random pseudo-polynomial algorithm for the problem of finding a base of specified value in a weighted represented matroid, subject to parity conditions. We also describe a specialized version of the algorithm suitable for finding a base of specified value in the intersection of two matroids. This result generalizes an existing pseudo-polynomial algorithm for computing exact arborescences in weighted graphs. Another (simpler) specialized version of our algorithms is also presented for computing perfect matchings of specified value in weighted graphs. © 1992.

引用

页码：258 / 273

页数：16

共 29 条

[1]

ADELMAN L, 9TH P ACM S THEOR CO, P151

[2]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[3] EXACT ARBORESCENCES, MATCHINGS AND CYCLES [J].

BARAHONA, F ;

PULLEYBLANK, WR .

DISCRETE APPLIED MATHEMATICS, 1987, 16 (02) :91-99

[4]

BARAHONA F, 1981, BALANCING SIGNED TOR

[5] 2 ALGORITHMS FOR WEIGHTED MATROID INTERSECTION [J].

BREZOVEC, C ;

CORNUEJOLS, G ;

GLOVER, F .

MATHEMATICAL PROGRAMMING, 1986, 36 (01) :39-53

[6] MULTI-CONSTRAINED MATROIDAL KNAPSACK-PROBLEMS [J].

CAMERINI, PM ;

MAFFIOLI, F ;

VERCELLIS, C .

MATHEMATICAL PROGRAMMING, 1989, 45 (02) :211-231

[7] UNLABELED PARTITION SYSTEMS - OPTIMIZATION AND COMPLEXITY [J].

CAMERINI, PM ;

MAFFIOLI, F .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (03) :426-441

[8]

CAMERINI PM, 1989, SIAM J DISCRETE MATH, V1, P16

[9]

CAMERINI PM, 1987, 87014 POL MIL DIP EL

[10]

CORNEUJOLS G, 1986, MAR WORK C COMP ISS

← 1 2 3 →