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.
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
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⟩
