Routing in Undirected Graphs with Constant Congestion
From MaRDI portal
Publication:2817791
DOI10.1137/130910464zbMath1350.68207OpenAlexW2515641369MaRDI QIDQ2817791
Publication date: 2 September 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.385.9241
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Flows in graphs (05C21)
Related Items
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Unnamed Item ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Edge-disjoint paths in planar graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Approximations for the disjoint paths problem in high-diameter planar networks
- Approximating disjoint-path problems using packing integer programs
- Graph minors. XIII: The disjoint paths problem
- Combinatorial algorithms for the unsplittable flow problem
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Edge-Disjoint Paths in Expander Graphs
- Random Sampling in Cut, Flow, and Network Design Problems
- Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
- The All-or-Nothing Multicommodity Flow Problem
- Extensions and limits to vertex sparsification
- An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- Almost-tight hardness of directed congestion minimization
- A constructive proof of the general lovász local lemma
- Multicommodity demand flow in a tree and packing integer programs
- Multicommodity flow, well-linked terminals, and routing problems
- Hardness of the undirected edge-disjoint paths problem
- Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- A Reduction Method for Edge-Connectivity in Graphs
- Existence and Construction of Edge-Disjoint Paths on Expander Graphs
- Reducibility among Combinatorial Problems
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Polynomial bounds for the grid-minor theorem
- Degree-3 Treewidth Sparsifiers
- On vertex sparsifiers with Steiner nodes
- Breaking o(n 1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two
- Hardness of the Undirected Congestion Minimization Problem
- Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
- Large-treewidth graph decompositions and applications
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
- Vertex Sparsifiers: New Results from Old Techniques
- Edge Disjoint Paths in Moderately Connected Graphs
- Concentration of Measure for the Analysis of Randomized Algorithms
- Expander flows, geometric embeddings and graph partitioning
- Graph partitioning using single commodity flows
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
