• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the linear relaxation of the 2-node connected subgraph polytope

Thumbnail
Date
1999
Dewey
Recherche opérationnelle
Sujet
Cut; Polytopes; Critical extreme point; 2-node connected graph
Journal issue
Discrete Applied Mathematics
Volume
95
Number
1-3
Publication date
07-1999
Article pages
389-416
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/S0166-218X(99)00088-8
URI
https://basepub.dauphine.fr/handle/123456789/3947
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Mahjoub, Ali Ridha
Nocq, Charles
Type
Article accepté pour publication ou publié
Abstract (EN)
In this paper, we study the linear relaxation P(G) of the 2-node connected subgraph polytope of a graph G. We introduce an ordering on the fractional extreme points of P(G) and we give a characterization of the minimal extreme points with respect to that ordering. This yields a polynomial method to separate a minimal extreme point of P(G) from the 2-node connected subgraph polytope. It also provides a new class of facet defining inequalities for this polytope.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.