Circuit and bond polytopes on series–parallel graphs - Archive ouverte HAL Access content directly
Journal Articles Discrete Optimization Year : 2015

Circuit and bond polytopes on series–parallel graphs

(1) , (2) , (1) , (1) , (3, 4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
CircuitsAndBondsInSP.pdf (161.29 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01215899 , version 1 (05-12-2017)

Identifiers

Cite

Sylvie Borne, Pierre Fouilhoux, Roland Grappe, Mathieu Lacroix, Pierre Pesneau. Circuit and bond polytopes on series–parallel graphs. Discrete Optimization, 2015, 17, pp.55-68. ⟨10.1016/j.disopt.2015.04.001⟩. ⟨hal-01215899⟩
260 View
147 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More