Name
Abstract | ||
|---|---|---|
In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight @m, we define a metrized polyhedral complex, called the directed tight span T"@m, and prove that the dual of the @m-weighted maximum multiflow problem reduces to a facility location problem on T"@m. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by @m. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial min-max relation (i) for every network and (ii) for every Eulerian network. Our result includes the Lomonosov-Frank theorem for directed free multiflows and Ibaraki-Karzanov-Nagamochi's directed multiflow locking theorem as special cases. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.disopt.2011.03.001 | Discrete Optimization |
Keywords | Field | DocType |
min–max theorems,special case,multicommodity flow,multicommodity flows,metrized polyhedral complex,eulerian network,combinatorial min-max relation,facility location problem,free multiflows,metrics,90c27,facility locations,terminal weight,m-weighted maximum multiflow problem,05c21,lomonosov-frank theorem,facility location | Discrete mathematics,Mathematical optimization,Combinatorics,Tight span,Facility location problem,Polytope,Duality (optimization),Eulerian path,Multi-commodity flow problem,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 3 | Discrete Optimization |
Citations | PageRank | References |
2 | 0.46 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiroshi Hirai | 1 | 8 | 2.99 |
| Shungo Koichi | 2 | 7 | 1.61 |