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
Contributeur : Pierre Pesneau
<>
Soumis le : mardi 5 décembre 2017 - 11:09:49
Dernière modification le : mercredi 21 mars 2018 - 18:58:11
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〉
