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

DOI10.1007/S10107-014-0856-ZMaRDI QIDQ896267zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• The all-or-nothing multicommodity flow problem
• The all-or-nothing multicommodity flow problem
• Publication:4598139
• Multiflows in symmetric digraphs

Cites work

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

Cited in

(7)

• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• Planar Digraphs
• The all-or-nothing multicommodity flow problem
• Multiflows in symmetric digraphs
• The all-or-nothing multicommodity flow problem
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• Constant congestion routing of symmetric demands in planar directed 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)