K-edge connected polyhedra on series-parallel graphs

被引：27

作者：

Biha, MD ^{[1
]}

Mahjoub, AR ^{[1
]}

机构：

[1] UNIV BRETAGNE OCCIDENTALE,DEPT INFORMAT,LAB SPO,F-29285 BREST,FRANCE

来源：

OPERATIONS RESEARCH LETTERS | 1996年 / 19卷 / 02期

关键词：

k-edge connected subgraphs; polytopes; series-parallel graphs;

D O I：

10.1016/0167-6377(96)00015-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We give a complete description of the k-edge connected spanning subgraph polytope (for all k) on series-parallel graphs.

引用

页码：71 / 78

页数：8

共 27 条

[1]

BAIOU M, IN PRESS SIAM J DISC

[2] On two-connected subgraph polytopes [J].

Barahona, F ;

Mahjoub, AR .

DISCRETE MATHEMATICS, 1995, 147 (1-3) :19-34

[3] SEPARATING FROM THE DOMINANT OF THE SPANNING TREE POLYTOPE [J].

BARAHONA, F .

OPERATIONS RESEARCH LETTERS, 1992, 12 (04) :201-203

[4] ON THE STRUCTURE OF MINIMUM-WEIGHT K-CONNECTED SPANNING NETWORKS [J].

BIENSTOCK, D ;

BRICKELL, EF ;

MONMA, CL .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (03) :320-329

[5] THE K-EDGE-CONNECTED SPANNING SUBGRAPH POLYHEDRON [J].

CHOPRA, S .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) :245-259

[6]

CHOPRA S, COMMUNICATION

[7]

Christofides N., 1981, Operational Research '81. Proceedings of the Ninth IFORS International Conference, P705

[8] THE TRAVELING SALESMAN PROBLEM ON A GRAPH AND SOME RELATED INTEGER POLYHEDRA [J].

CORNUEJOLS, G ;

FONLUPT, J ;

NADDEF, D .

MATHEMATICAL PROGRAMMING, 1985, 33 (01) :1-27

[9]

COULLARD R, CC9123 PURD U SCH IN

[10]

COULLARD R, 9128 PURD U SCH IND

← 1 2 3 →