Trader multiflow and box-TDI systems in series–parallel graphs
2019
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
20
References
3
Citations
NaN
KQI