Circuit and bond polytopes on series–parallel graphs
PESNEAU, Pierre
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
< Leer menos
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Idioma
en
Article de revue
Este ítem está publicado en
Discrete Optimization. 2015-08, vol. 17, p. 55–68
Elsevier
Resumen en inglés
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 ...Leer más >
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.< Leer menos
Palabras clave en inglés
Extended formulation
Series–parallel graph
Circuit polytope
series-parallel graph
Bond polytope
Orígen
Importado de HalCentros de investigación