Skip to Main content Skip to Navigation
Journal articles

Trader multiflow and box-TDI systems in series-parallel graphs

Abstract : Series–parallel graphs are known to be precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone, the T-join polytope, the cut polytope, the multicut polytope and the T-join dominant are TDI. We prove that these systems are actually box-TDI. As a byproduct, our result yields a min–max relation for a new problem: the trader multiflow problem. The latter generalizes both the maximum multiflow and min-cost multiflow problems and we show that it is polynomial-time solvable in series–parallel graphs.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02186541
Contributor : Accord Elsevier Ccsd Connect in order to contact the contributor
Submitted on : Friday, October 22, 2021 - 11:07:17 AM
Last modification on : Wednesday, November 17, 2021 - 12:27:16 PM

File

S1572528618301117.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

Citation

Denis Cornaz, Roland Grappe, Mathieu Lacroix. Trader multiflow and box-TDI systems in series-parallel graphs. Discrete Optimization, Elsevier, 2019, 31 (1), ⟨10.1016/j.disopt.2018.09.003⟩. ⟨hal-02186541⟩

Share

Metrics

Les métriques sont temporairement indisponibles