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

DOI10.1007/S10107-014-0856-ZzbMATH Open1337.90018OpenAlexW2127985326MaRDI QIDQ896267FDOQ896267

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) Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Flows in graphs (05C21)

Cites Work

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

Cited In (3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896267)