| dc.contributor.author | Cornaz, Denis | |
| dc.contributor.author | Grappe, Roland | |
| dc.contributor.author | Lacroix, Mathieu | |
| dc.date.accessioned | 2019-07-17T10:34:09Z | |
| dc.date.available | 2019-07-17T10:34:09Z | |
| dc.date.issued | 2019 | |
| dc.identifier.issn | 1572-5286 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/19250 | |
| dc.language.iso | en | en |
| dc.subject | Box-TDI system | en |
| dc.subject | Series–parallel graph | en |
| dc.subject | Multiflow | en |
| dc.subject.ddc | 518 | en |
| dc.title | Trader multiflow and box-TDI systems in series-parallel graphs | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | 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. | en |
| dc.relation.isversionofjnlname | Discrete Optimization | |
| dc.relation.isversionofjnlvol | 31 | en |
| dc.relation.isversionofjnlissue | 1 | en |
| dc.relation.isversionofjnldate | 2019-02 | |
| dc.relation.isversionofjnlpages | 103-114 | en |
| dc.relation.isversionofdoi | 10.1016/j.disopt.2018.09.003 | en |
| dc.relation.isversionofjnlpublisher | Elsevier | en |
| dc.subject.ddclabel | Modèles mathématiques. Algorithmes | en |
| dc.relation.forthcoming | non | en |
| dc.relation.forthcomingprint | non | en |
| dc.description.ssrncandidate | non | en |
| dc.description.halcandidate | oui | en |
| dc.description.readership | recherche | en |
| dc.description.audience | International | en |
| dc.relation.Isversionofjnlpeerreviewed | oui | en |
| dc.relation.Isversionofjnlpeerreviewed | oui | en |
| dc.date.updated | 2019-07-17T10:32:10Z | |
| hal.person.labIds | 989 | |
| hal.person.labIds | 994 | |
| hal.person.labIds | 994 | |
| hal.identifier | hal-02186541 | * |
