Matching, matroids, and extensions

被引：33
作者：
Cunningham, WH [1 ]
机构：
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
来源：
MATHEMATICAL PROGRAMMING | 2002年 / 91卷 / 03期
关键词：
D O I：
10.1007/s101070100256
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Perhaps the two most fundamental well-solved models in combinatorial optimization are the optimal matching problem and the optimal matroid intersection problem. We review & basic results for both, and describe sonic more recent advances. Then we discuss extensions of these models, in particular, two recent ones-jump systems and path-matchings.
引用
收藏
页码：515 / 542
页数：28
相关论文
共 42 条
[1]  
[Anonymous], THESIS U WATERLOO
[2]  
Bixby R, 1995, HDB COMBINATORICS, P550
[3]   DELTA-MATROIDS, JUMP SYSTEMS, AND BISUBMODULAR POLYHEDRA [J].
BOUCHET, A ;
CUNNINGHAM, WH .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (01) :17-32
[4]   GREEDY ALGORITHM AND SYMMETRICAL MATROIDS [J].
BOUCHET, A .
MATHEMATICAL PROGRAMMING, 1987, 38 (02) :147-159
[5]   PSEUDOMATROIDS [J].
CHANDRASEKARAN, R ;
KABADI, SN .
DISCRETE MATHEMATICS, 1988, 71 (03) :205-217
[6]  
Cook W., 1998, Combinatorial Optimization
[7]   MATCHING PROBLEM WITH SIDE CONDITIONS [J].
CORNUEJOLS, G ;
PULLEYBLANK, W .
DISCRETE MATHEMATICS, 1980, 29 (02) :135-159
[8]   The optimal path-matching problem [J].
Cunningham, WH ;
Geelen, JF .
COMBINATORICA, 1997, 17 (03) :315-337
[9]  
CUNNINGHAM WH, 1978, MATH PROGRAM STUD, V8, P50, DOI 10.1007/BFb0121194
[10]  
CUNNINGHAM WH, 2000, UNPUB COMBINATORIAL
12345