A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.

DOI10.4230/LIPIcs.MFCS.2020.68OpenAlexW3212146959MaRDI QIDQ5089241

Ignasi Sau, Raul Lopes

Publication date: 18 July 2022

Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2020.html#0001S20

zbMATH Keywords

congestionparameterized complexitykernelizationdirected tree-widthdual parameterizationdirected disjoint paths

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Adapting the Directed Grid Theorem into an FPT Algorithm

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.