The all-or-nothing flow problem in directed graphs with symmetric demand pairs
DOI10.1007/S10107-014-0856-ZzbMATH Open1337.90018OpenAlexW2127985326MaRDI QIDQ896267FDOQ896267
Authors: 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
Recommendations
Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Flows in graphs (05C21)
Cites Work
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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 (7)
- The all-or-nothing multicommodity flow problem
- Multiflows in symmetric digraphs
- The all-or-nothing flow problem in directed graphs with symmetric demand pairs
- Constant congestion routing of symmetric demands in planar directed graphs
- Planar Digraphs
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
- The all-or-nothing multicommodity flow problem
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)
