Routing with congestion in acyclic digraphs
From MaRDI portal
Publication:2274522
DOI10.1016/j.ipl.2019.105836zbMath1461.05098OpenAlexW2964013645MaRDI QIDQ2274522
Stephan Kreutzer, Roman Rabinovich, Saeed Akhoondian Amiri, Dániel Marx
Publication date: 20 September 2019
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6424/
algorithmscongestionacyclic digraphsdisjoint pathsW[1-hard problem]
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Graph minors XXIII. Nash-Williams' immersion conjecture
- The directed subgraph homeomorphism problem
- Approximating disjoint-path problems using packing integer programs
- Which problems have strongly exponential complexity?
- Directed tree-width
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Multicommodity flow, well-linked terminals, and routing problems
- On the Complexity of Timetable and Multicommodity Flow Problems
- Vertex Disjoint Paths in Upward Planar Graphs
- Congestion-Free Rerouting of Flows on DAGs
- Approximation algorithms and hardness of integral concurrent flow
- The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
- Parameterized Algorithms
- Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
- Spectral Theory and Analysis
