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, dans 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érenceDate
1999Titre du colloque
7th International IPCO Conference (IPCO'99)Date du colloque
1999-06Ville du colloque
GrazPays du colloque
AutricheTitre de l'ouvrage
Integer Programming and Combinatorial Optimization 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, ProceedingsAuteurs de l’ouvrage
Woeginger, Gerhard J.; Burkard, Rainer E.; Cornuejols, GérardÉditeur
Springer
Titre de la collection
Lecture Notes in Computer ScienceNuméro dans la collection
1610Ville d’édition
Berlin
Isbn
978-3-540-66019-4
Nombre de pages
453Pages
166-182
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (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.Mots-clés
Polytope; cut; 2-edge connected graph; critical extreme pointPublications associées
Affichage des éléments liés par titre et auteur.
-
Fonlupt, Jean; Mahjoub, Ali Ridha (2006) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2004) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Pesneau, Pierre (2008) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Nocq, Charles (1999) Article accepté pour publication ou publié
-
Baïou, Mourad; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié