A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
From MaRDI portal
Publication:5089241
DOI10.4230/LIPIcs.MFCS.2020.68OpenAlexW3212146959MaRDI QIDQ5089241
Publication date: 18 July 2022
Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2020.html#0001S20
congestionparameterized complexitykernelizationdirected tree-widthdual parameterizationdirected disjoint paths
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
- The directed subgraph homeomorphism problem
- Highly connected non-2-linked digraphs
- Directed tree-width
- Graph minors. XIII: The disjoint paths problem
- Routing with congestion in acyclic digraphs
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- The Directed Grid Theorem
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Finding k Disjoint Paths in a Directed Planar Graph
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Close Encounters with the Stirling Numbers of the Second Kind
- Dual parameterization of Weighted Coloring
- Half-integral linkages in highly connected directed graphs
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- Partially Polynomial Kernels for Set Cover and Test Cover
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
This page was built for publication: A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.