• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Critical extreme points of the 2-edge connected spanning subgraph polytope

Fonlupt, Jean; Mahjoub, Ali Ridha (1999), Critical extreme points of the 2-edge connected spanning subgraph polytope, in Woeginger, Gerhard J.; Burkard, Rainer E.; Cornuejols, Gérard, Integer Programming and Combinatorial Optimization 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings, Springer : Berlin, p. 166-182. http://dx.doi.org/10.1007/3-540-48777-8_13

Type
Communication / Conférence
Date
1999
Conference title
7th International IPCO Conference (IPCO'99)
Conference date
1999-06
Conference city
Graz
Conference country
Autriche
Book title
Integer Programming and Combinatorial Optimization 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings
Book author
Woeginger, Gerhard J.; Burkard, Rainer E.; Cornuejols, Gérard
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
1610
Published in
Berlin
ISBN
978-3-540-66019-4
Number of pages
453
Pages
166-182
Publication identifier
http://dx.doi.org/10.1007/3-540-48777-8_13
Metadata
Show full item record
Author(s)
Fonlupt, Jean
Mahjoub, Ali Ridha
Abstract (EN)
In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if $ \bar x$x is a non-integer minimal extreme point of P(G), then G and $ \bar x$x can be reduced, by means of some reduction operations, to a graph G′ and an extreme point $ \bar x'$x of P(G′) where G′ and $ \bar x'$x satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral.
Subjects / Keywords
Polytope; cut; 2-edge connected graph; critical extreme point

Related items

Showing items related by title and author.

  • Thumbnail
    Critical extreme points of the 2-edge connected subgraph polytope 
    Fonlupt, Jean; Mahjoub, Ali Ridha (2006) Article accepté pour publication ou publié
  • Thumbnail
    The k-edge subgraph problem I: Critical extreme points 
    Didi Biha, Mohamed; Mahjoub, Ali Ridha (2004) Article accepté pour publication ou publié
  • Thumbnail
    On the Steiner 2-edge connected subgraph polytope 
    Mahjoub, Ali Ridha; Pesneau, Pierre (2008) Article accepté pour publication ou publié
  • Thumbnail
    On the linear relaxation of the 2-node connected subgraph polytope 
    Mahjoub, Ali Ridha; Nocq, Charles (1999) Article accepté pour publication ou publié
  • Thumbnail
    Steiner 2-edge connected subgraph polytopes on series-parallel graphs 
    Baïou, Mourad; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo