Circuit and bond polytopes on series–parallel graphs

Abstract : In this paper, we describe the circuit polytope on series–parallel graphs. We first show the existence of a compact extended formulation. Though not being explicit, its construction process helps us to inductively provide the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe the bond polytope on series–parallel graphs.
Type de document :
Article dans une revue
Discrete Optimization, Elsevier, 2015, 17, pp.55-68. 〈10.1016/j.disopt.2015.04.001〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01215899
Contributeur : Pierre Pesneau <>
Soumis le : mardi 5 décembre 2017 - 11:09:49
Dernière modification le : jeudi 11 janvier 2018 - 06:27:16

Fichier

CircuitsAndBondsInSP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Sylvie Borne, Pierre Fouilhoux, Roland Grappe, Mathieu Lacroix, Pierre Pesneau. Circuit and bond polytopes on series–parallel graphs. Discrete Optimization, Elsevier, 2015, 17, pp.55-68. 〈10.1016/j.disopt.2015.04.001〉. 〈hal-01215899〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

8