Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141661 | Discrete Optimization | 2015 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Sylvie Borne, Pierre Fouilhoux, Roland Grappe, Mathieu Lacroix, Pierre Pesneau,