On duality and fractionality of multicommodity flows in directed networks

DOI10.1016/j.disopt.2011.03.001zbMath1261.90044arXiv1006.5520MaRDI QIDQ665994

Hiroshi Hirai, Shungo Koichi

Publication date: 7 March 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.5520

zbMATH Keywords

multicommodity flows; metrics; min-max theorems; facility locations

Mathematics Subject Classification ID

90C27: Combinatorial optimization

05C21: Flows in graphs

Related Items

On tight spans for directed distances, Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, Euler Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Polyhedra related to undirected multicommodity flows
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• Tropical convexity
• On tight spans for directed distances
• Characterization of the distance between subtrees of a tree by the associated tight span
• Six theorems about injective metric spaces
• Folder Complexes and Multiflow Combinatorial Dualities