Constant congestion routing of symmetric demands in planar directed graphs
DOI10.1137/17M1150694zbMATH Open1398.68391WikidataQ129353744 ScholiaQ129353744MaRDI QIDQ4582017FDOQ4582017
Marcin Pilipczuk, Chandra Chekuri, Alina Ene
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
- The directed subgraph homeomorphism problem
- Directed tree-width
- Graph minors. XIII: The disjoint paths problem
- Introducing directed tree width
- Approximation Algorithms for Steiner and Directed Multicuts
- Parameterized Algorithms
- Quickly excluding a planar graph
- On Independent Circuits Contained in a Graph
- Large-treewidth graph decompositions and applications
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- On the Computational Complexity of Combinatorial Problems
- Excluded Grid Theorem
- Title not available (Why is that?)
- The Gallai-Younger conjecture for planar graphs
- Packing directed circuits
- Linearity of grid minors in treewidth with applications through bidimensionality
- Multicommodity flow, well-linked terminals, and routing problems
- Divide-and-conquer approximation algorithms via spreading metrics
- Packing directed circuits fractionally
- Title not available (Why is that?)
- Approximating disjoint-path problems using packing integer programs
- Multicommodity flows and cuts in polymatroidal networks
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Title not available (Why is that?)
- New hardness results for routing on disjoint paths
- Routing in undirected graphs with constant congestion
- The all-or-nothing multicommodity flow problem
- Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
- The all-or-nothing flow problem in directed graphs with symmetric demand pairs
- Degree-3 Treewidth Sparsifiers
- An Excluded Grid Theorem for Digraphs with Forbidden Minors
- The Directed Grid Theorem
- Improved approximation for node-disjoint paths in planar graphs
- Edge Disjoint Paths in Moderately Connected Graphs
- Polynomial Bounds for the Grid-Minor Theorem
- Graph partitioning using single commodity flows
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach
- Network Capacity Under Traffic Symmetry: Wireline and Wireless Networks
- Title not available (Why is that?)
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)
