Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Pierre Pesneau Connect in order to contact the contributor
Submitted on : Tuesday, December 5, 2017 - 11:09:49 AM
Last modification on : Tuesday, October 19, 2021 - 11:05:59 PM


Files produced by the author(s)



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⟩



Record views


Files downloads