On two-connected subgraph polytopes

被引：35

作者：

Barahona, F

Mahjoub, AR

机构：

[1] IBM CORP,THOMAS J WATSON RES CTR,YORKTOWN HTS,NY 10598

[2] UNIV BRETAGNE OCCIDENTALE,DEPT INFORMAT,F-29285 BREST,FRANCE

来源：

DISCRETE MATHEMATICS | 1995年 / 147卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(94)00255-H

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We further study some known families of valid inequalities for the 2-edge-connected and 2-node-connected subgraph polytopes. For the 2-edge-connected case, we show that the odd wheel inequalities together with the obvious constraints give a complete description of the polytope for Halin graphs. For 2-node-connected subgraphs, we show that the inequalities above, plus the partition inequalities, describe the polytope for the same class of graphs.

引用

收藏

页码：19 / 34

页数：16

相关论文

共 16 条

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

BARAHONA, F .

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

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

CHOPRA, S .

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

[3] ON THE SPANNING TREE POLYHEDRON [J].

CHOPRA, S .

OPERATIONS RESEARCH LETTERS, 1989, 8 (01) :25-29

[4] POLYHEDRA OF THE EQUIVALENT SUBGRAPH PROBLEM AND SOME EDGE CONNECTIVITY PROBLEMS [J].

CHOPRA, S .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (03) :321-337

[5] HALIN GRAPHS AND THE TRAVELING SALESMAN PROBLEM [J].

CORNUEJOLS, G ;

NADDEF, D ;

PULLEYBLANK, WR .

MATHEMATICAL PROGRAMMING, 1983, 26 (03) :287-294

[6]

COULLARD C, 1991, CC9128 PURD U SCH IN

[7] OPTIMAL ATTACK AND REINFORCEMENT OF A NETWORK [J].

CUNNINGHAM, WH .

JOURNAL OF THE ACM, 1985, 32 (03) :549-561

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

[9] FACETS FOR POLYHEDRA ARISING IN THE DESIGN OF COMMUNICATION NETWORKS WITH LOW-CONNECTIVITY CONSTRAINTS [J].

Groetschel, Martin ;

Monma, Clyde L. ;

Stoer, Mechthild .

SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (03) :474-504

[10] COMPUTATIONAL RESULTS WITH A CUTTING PLANE ALGORITHM FOR DESIGNING COMMUNICATION-NETWORKS WITH LOW-CONNECTIVITY CONSTRAINTS [J].

GROTSCHEL, M ;

MONMA, CL ;

STOER, M .

OPERATIONS RESEARCH, 1992, 40 (02) :309-330