Bounded fractionality of the multiflow feasibility problem for demand graph \(K_3 + K_3\) and related maximization problems

DOI10.1016/j.jctb.2012.02.001zbMath1246.05068MaRDI QIDQ444377

Hiroshi Hirai

Publication date: 14 August 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2012.02.001

zbMATH Keywords

multicommodity flows; metrics; fractionality; demand graph; multiflow feasability problem

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C22: Signed and weighted graphs

05C21: Flows in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Half-integral five-terminus flows
• 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
• Combinatorial approaches to multiflow problems
• Polyhedra related to undirected multicommodity flows
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Minimum \((2,r)\)-metrics and integer multiflows
• Graphs of some CAT(0) complexes
• Six theorems about injective metric spaces
• Folder Complexes and Multiflow Combinatorial Dualities
• Four-terminus flows
• Feasibility of Two Commodity Network Flows
• Multi-Commodity Network Flows