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

被引：5

作者：

Cornaz, Denis ^{[1
]}

Grappe, Roland ^{[2
]}

Lacroix, Mathieu ^{[2
]}

机构：

[1] Univ Paris 09, Pl Marechal Lattre Tassigny, F-75775 Paris 16, France

[2] Univ Paris 13, Sorbonne Paris Cite, LIPN, CNRS UMR 7030, F-93430 Villetaneuse, France

来源：

DISCRETE OPTIMIZATION | 2019年 / 31卷

关键词：

Box-TDI system; Series-parallel graph; Multiflow; CUT; POLYTOPE;

D O I：

10.1016/j.disopt.2018.09.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：103 / 114

页数：12

共 21 条

[1] ON THE CUT POLYTOPE [J].