A relaxation of the directed disjoint paths problem: a global congestion metric helps

DOI10.1016/j.tcs.2021.10.023OpenAlexW3082444755MaRDI QIDQ2055975

Raul Lopes, Ignasi Sau

Publication date: 1 December 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.13848

zbMATH Keywords

congestionparameterized complexitykernelizationdirected tree-widthdual parameterizationdirected disjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Graph minors. V. Excluding a planar graph
• The directed subgraph homeomorphism problem
• Highly connected non-2-linked digraphs
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• Adapting the directed grid theorem into an \textsf{FPT} algorithm
• Routing with congestion in acyclic digraphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Directed tree-width examples
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• Tour Merging via Branch-Decomposition
• The Directed Grid Theorem
• Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Finding k Disjoint Paths in a Directed Planar Graph
• Classes of Directed Graphs
• 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
• The Directed Flat Wall Theorem
• 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