Circuit and bond polytopes on series–parallel graphs

Sylvie Borne; Pierre Fouilhoux; Roland Grappe; Mathieu Lacroix; Pierre Pesneau

doi:10.1016/j.disopt.2015.04.001

Journal articles

Circuit and bond polytopes on series–parallel graphs

Sylvie Borne ¹ Pierre Fouilhoux ² Roland Grappe ¹ Mathieu Lacroix ¹ Pierre Pesneau ^{3, 4}

1 LIPN - Laboratoire d'Informatique de Paris-Nord

2 RO - Recherche Opérationnelle

LIP6 - Laboratoire d'Informatique de Paris 6

3 Realopt - Reformulations based algorithms for Combinatorial Optimization

LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest

4 IMB - Institut de Mathématiques de Bordeaux

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.

Keywords : Bond polytope Extended formulation Circuit polytope Series–parallel graph series-parallel graph

Document type :

Journal articles

Domain :

Computer Science [cs] / Operations Research [cs.RO]

Complete list of metadata

Cited literature [22 references] Display Hide Download

https://hal.inria.fr/hal-01215899
Contributor : Pierre Pesneau Connect in order to contact the contributor
Submitted on : Tuesday, December 5, 2017 - 11:09:49 AM
Last modification on : Tuesday, October 19, 2021 - 11:05:59 PM

Circuit and bond polytopes on series–parallel graphs

File

Identifiers

Collections

Citation

Export

Metrics

630

804

Contact Legal Notice Personal Data

Circuit and bond polytopes on series–parallel graphs

File

Identifiers

Collections

Citation

Export

Share

Metrics

630

804

Contact Legal Notice Personal Data