Circuit and bond polytopes on series–parallel graphs

Sylvie Borne 1 Pierre Fouilhoux 2 Roland Grappe 1 Mathieu Lacroix 1 Pierre Pesneau 3, 4
2 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215899
Contributor : Pierre Pesneau <>
Submitted on : Tuesday, December 5, 2017 - 11:09:49 AM
Last modification on : Friday, May 24, 2019 - 5:25:42 PM

File

CircuitsAndBondsInSP.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

497

Files downloads

409