Skip to Main content Skip to Navigation
Journal articles

The st-bond polytope on series-parallel graphs

Abstract : The st-bond polytope of a graph is the convex hull of the incidence vectors of its st-bonds, where an st-bond is a minimal st-cut. In this paper, we provide a linear description of the st-bond polytope on series-parallel graphs. We also show that the st-bond polytope is the intersection of the st-cut dominant and the bond polytope.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02925349
Contributor : Edp Sciences <>
Submitted on : Saturday, August 29, 2020 - 11:48:59 AM
Last modification on : Wednesday, December 9, 2020 - 10:26:07 AM

File

ro160245.pdf
Publication funded by an institution

Identifiers

Collections

Citation

Roland Grappe, Mathieu Lacroix. The st-bond polytope on series-parallel graphs. RAIRO - Operations Research, EDP Sciences, 2018, 52 (3), pp.923-934. ⟨10.1051/ro/2018035⟩. ⟨hal-02925349⟩

Share

Metrics

Record views

42

Files downloads

68