Constant congestion routing of symmetric demands in planar directed graphs
DOI10.1137/17M1150694zbMATH Open1398.68391WikidataQ129353744 ScholiaQ129353744MaRDI QIDQ4582017FDOQ4582017
Authors: Chandra Chekuri, Alina Ene, Marcin Pilipczuk 
Publication date: 22 August 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Recommendations
Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- An excluded grid theorem for digraphs with forbidden minors
- Approximating disjoint-path problems using packing integer programs
- Approximation Algorithms for Steiner and Directed Multicuts
- Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach
- Degree-3 treewidth sparsifiers
- Directed tree-width
- Divide-and-conquer approximation algorithms via spreading metrics
- Edge Disjoint Paths in Moderately Connected Graphs
- Excluded grid theorem: improved and simplified
- Graph minors. XIII: The disjoint paths problem
- Graph partitioning using single commodity flows
- Improved approximation for node-disjoint paths in planar graphs
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Introducing directed tree width
- Large-treewidth graph decompositions and applications
- Linearity of grid minors in treewidth with applications through bidimensionality
- Multicommodity flow, well-linked terminals, and routing problems
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Network Capacity Under Traffic Symmetry: Wireline and Wireless Networks
- New hardness results for routing on disjoint paths
- On Independent Circuits Contained in a Graph
- On the Computational Complexity of Combinatorial Problems
- Packing directed circuits
- Packing directed circuits fractionally
- Parameterized algorithms
- Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
- Polynomial bounds for the grid-minor theorem
- Quickly excluding a planar graph
- Routing in undirected graphs with constant congestion
- The Gallai-Younger conjecture for planar graphs
- The all-or-nothing flow problem in directed graphs with symmetric demand pairs
- The all-or-nothing multicommodity flow problem
- The directed grid theorem
- The directed subgraph homeomorphism problem
Cited In (4)
This page was built for publication: Constant congestion routing of symmetric demands in planar directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4582017)
