ON CUTS AND MATCHINGS IN PLANAR GRAPHS

被引：32

作者：

BARAHONA, F ^{[1
]}

机构：

[1] UNIV WATERLOO, DEPT COMBINATOR & OPTIMIZAT, WATERLOO N2L 3G1, ONTARIO, CANADA

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 60卷 / 01期

关键词：

CUT POLYTOPE; MATCHING; MULTICOMMODITY FLOWS;

D O I：

10.1007/BF01580600

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study the max cut problem in graphs not contractible to K5, and optimum perfect matchings in planar graphs. We prove that both problems can be formulated as polynomial size linear programs.

引用

页码：53 / 68

页数：16

共 24 条

[1]

BALL M., 1987, 87466OR U BONN I OP

[2] ON THE CUT POLYTOPE [J].

BARAHONA, F ;

MAHJOUB, AR .

MATHEMATICAL PROGRAMMING, 1986, 36 (02) :157-173

[3] ON SOME WEAKLY BIPARTITE GRAPHS [J].

BARAHONA, F .

OPERATIONS RESEARCH LETTERS, 1983, 2 (05) :239-242

[4] THE MAX-CUT PROBLEM ON GRAPHS NOT CONTRACTIBLE TO K5 [J].

BARAHONA, F .

OPERATIONS RESEARCH LETTERS, 1983, 2 (03) :107-111

[5]

BARAHONA F, IN PRESS SIAM J DISC

[6]

BARAHONA F, 1989, IN PRESS SIAM J DISC

[7]

Barahona F., 1990, DIMACS SERIES DISCRE, P189

[8]

BARAHONA F, 1988, IN PRESS SIAM J OPTI

[9]

BARAHONA F, 1986, CORR8616 U WAT RES R

[10] THE TRAVELING SALESMAN PROBLEM IN GRAPHS WITH 3-EDGE CUTSETS [J].

CORNUEJOLS, G ;

NADDEF, D ;

PULLEYBLANK, W .

JOURNAL OF THE ACM, 1985, 32 (02) :383-410

← 1 2 3 →