The all-or-nothing flow problem in directed graphs with symmetric demand pairs

DOI10.1007/s10107-014-0856-zzbMath1337.90018OpenAlexW2127985326MaRDI QIDQ896267

Chandra Chekuri, Alina Ene

Publication date: 9 December 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/65523/1/WRAP_Ene_dir-anf-journal%20%282%29.pdf

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)

Related Items (3)

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Planar Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A lower bound on the integrality gap for minimum multicut in directed networks
• The directed subgraph homeomorphism problem
• Directed tree-width
• The geometry of graphs and some of its algorithmic applications
• Directed tree-width examples
• Routing in Undirected Graphs with Constant Congestion
• Multicommodity flows and cuts in polymatroidal networks
• The All-or-Nothing Multicommodity Flow Problem
• Approximation Algorithms for Steiner and Directed Multicuts
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Polynomial flow-cut gaps and hardness of directed cut problems
• Multicommodity demand flow in a tree and packing integer programs
• Multicommodity flow, well-linked terminals, and routing problems
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• On the Complexity of Timetable and Multicommodity Flow Problems
• Reducibility among Combinatorial Problems
• Excluded minors, network decomposition, and multicommodity flow
• Polynomial bounds for the grid-minor theorem
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Large-treewidth graph decompositions and applications
• Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion

This page was built for publication: The all-or-nothing flow problem in directed graphs with symmetric demand pairs