• 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

Two edge connected spanning subgraphs and polyhedra

Mahjoub, Ali Ridha (1994), Two edge connected spanning subgraphs and polyhedra, Mathematical Programming, 64, 1-3, p. 199-208. http://dx.doi.org/10.1007/BF01582572

Type
Article accepté pour publication ou publié
Date
1994
Journal name
Mathematical Programming
Volume
64
Number
1-3
Publisher
Springer
Pages
199-208
Publication identifier
http://dx.doi.org/10.1007/BF01582572
Metadata
Show full item record
Author(s)
Mahjoub, Ali Ridha
Abstract (EN)
This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.
Subjects / Keywords
Series—parallel graphs; Facets; Polyhedra; Two-edge connected graphs

Related items

Showing items related by title and author.

  • Thumbnail
    Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut 
    Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié
  • Thumbnail
    Steiner k-edge connected subgraph polyhedra 
    Didi Biha, Mohamed; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
  • Thumbnail
    Critical extreme points of the 2-edge connected spanning subgraph polytope 
    Fonlupt, Jean; Mahjoub, Ali Ridha (1999) Communication / Conférence
  • Thumbnail
    Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs 
    Barahona, Francisco; Fonlupt, Jean; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
  • Thumbnail
    A Branch-and-Cut algorithm for the k-edge connected subgraph problem 
    Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) 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