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
    BARAHONA, F
    MAHJOUB, AR
    [J]. MATHEMATICAL PROGRAMMING, 1986, 36 (02) : 157 - 173
  • [3] ON SOME WEAKLY BIPARTITE GRAPHS
    BARAHONA, F
    [J]. OPERATIONS RESEARCH LETTERS, 1983, 2 (05) : 239 - 242
  • [4] THE MAX-CUT PROBLEM ON GRAPHS NOT CONTRACTIBLE TO K5
    BARAHONA, F
    [J]. 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
    CORNUEJOLS, G
    NADDEF, D
    PULLEYBLANK, W
    [J]. JOURNAL OF THE ACM, 1985, 32 (02) : 383 - 410
123