Routing with congestion in acyclic digraphs

DOI10.1016/J.IPL.2019.105836MaRDI QIDQ2274522zbMATH OpenOpenAlexFDO

Authors Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich

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/

zbMATH Keywords

acyclic digraphsalgorithmscongestiondisjoint pathsW[1-hard problem]

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 6851840
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Routing in undirected graphs with constant congestion
• Routing in undirected graphs with constant congestion
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs

Cites work

• Approximating disjoint-path problems using packing integer programs
• Approximation algorithms and hardness of integral concurrent flow
• Can you beat treewidth?
• Congestion-free rerouting of flows on DAGs
• Digraphs. Theory, algorithms and applications
• Directed tree-width
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph theory
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 6851840 (Why is no real title available?)
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Lower bounds based on the exponential time hypothesis
• Multicommodity flow, well-linked terminals, and routing problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parameterized algorithms
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• The directed subgraph homeomorphism problem
• Vertex disjoint paths in upward planar graphs
• Which problems have strongly exponential complexity?

Cited in

(17)

• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• A tight lower bound for edge-disjoint paths on planar DAGs
• scientific article; zbMATH DE number 3848940 (Why is no real title available?)
• Congestion-free Routings of Linear Complement Permutations
• scientific article; zbMATH DE number 6820196 (Why is no real title available?)
• scientific article; zbMATH DE number 6851840 (Why is no real title available?)
• A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
• On mergings in acyclic directed graphs
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• Constant congestion linkages in polynomially strong digraphs in polynomial time
• New Menger-like dualities in digraphs and applications to half-integral linkages
• Can you link up with treewidth?
• Can you link up with treewidth?
• Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
• Revisiting directed disjoint paths on tournaments (and relatives)

This page was built for publication: Routing with congestion in acyclic digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274522)