The k-edge connected subgraph problem I:: Polytopes and critical extreme points

被引：7
作者：
Biha, MD
Mahjoub, AR
机构：
[1] Univ Clermont Ferrand, CNRS, Lab LIMOS, UMR 6158, F-63177 Aubiere, France
[2] Univ Avignon, Lab Anal Non Lineaire & Geometrie, F-84911 Avignon, France
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2004年 / 381卷
关键词：
polytope; cut; k-edge connected graph; critical extreme point;
D O I：
10.1016/j.laa.2003.11.007
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper we consider the linear relaxation of the k-edge connected subgraph polytope, P(G, k), given by the trivial and the so-called cut inequalities. We introduce an ordering on the fractional extreme points of P(G, k) and describe some structural properties of the minimal extreme points with respect to that ordering. Using this we give sufficient conditions for P(G, k) to be integral. (C) 2003 Elsevier Inc. All rights reserved.
引用
收藏
页码：117 / 139
页数：23
相关论文
共 6 条
  • [1] Critical extreme points of the 2-edge connected spannning subgraph polytope
    Fonlupt, J
    Mahjoub, AR
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, 1999, 1610 : 166 - 182
  • [2] Critical extreme points of the 2-edge connected spanning subgraph polytope
    Fonlupt, J
    Mahjoub, AR
    MATHEMATICAL PROGRAMMING, 2006, 105 (2-3) : 289 - 310
  • [3] Critical extreme points of the 2-edge connected spanning subgraph polytope
    Jean Fonlupt
    A. Ridha Mahjoub
    Mathematical Programming, 2006, 105 : 289 - 310
  • [4] A Branch-and-Cut Algorithm for the k-Edge Connected Subgraph Problem
    Bendali, F.
    Diarrassouba, I.
    Mahjoub, A. R.
    Biha, M. Didi
    Mailfert, J.
    NETWORKS, 2010, 55 (01) : 13 - 32
  • [5] Steiner k-Edge Connected Subgraph Polyhedra
    M. Didi Biha
    A.R. Mahjoub
    Journal of Combinatorial Optimization, 2000, 4 : 131 - 144
  • [6] Steiner k-edge connected subgraph polyhedra
    Biha, MD
    Mahjoub, AR
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2000, 4 (01) : 131 - 144
1