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
1994Journal name
Mathematical ProgrammingVolume
64Number
1-3Publisher
Springer
Pages
199-208
Publication identifier
Metadata
Show full item recordAuthor(s)
Mahjoub, Ali RidhaAbstract (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 graphsRelated items
Showing items related by title and author.
-
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
-
Fonlupt, Jean; Mahjoub, Ali Ridha (1999) Communication / Conférence
-
Barahona, Francisco; Fonlupt, Jean; Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié