Circuit and bond polytopes on series–parallel graphs
PESNEAU, Pierre
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
< Reduce
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Language
en
Article de revue
This item was published in
Discrete Optimization. 2015-08, vol. 17, p. 55–68
Elsevier
English 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 ...Read more >
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.Read less <
English Keywords
Extended formulation
Series–parallel graph
Circuit polytope
series-parallel graph
Bond polytope
Origin
Hal imported