A relaxation of the directed disjoint paths problem: a global congestion metric helps
type: Item
instance of: scholarly article
title: A relaxation of the directed disjoint paths problem: a global congestion metric helps
author: Raul Lopes
author: Ignasi Sau
published in: Theoretical Computer Science
publication date: 2021-12-01T00:00:00Z
full work available at URL: https://arxiv.org/abs/1909.13848
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12737/
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7437226
zbMATH Keywords: parameterized complexity
zbMATH Keywords: directed disjoint paths
zbMATH Keywords: congestion
zbMATH Keywords: dual parameterization
zbMATH Keywords: kernelization
zbMATH Keywords: directed tree-width
MaRDI profile type: Publication
OpenAlex ID: W3082444755
cites work: Directed tree-width examples
cites work: Routing with congestion in acyclic digraphs
cites work: Dual parameterization of Weighted Coloring
cites work: Classes of Directed Graphs
cites work: Partially Polynomial Kernels for Set Cover and Test Cover
cites work: Close Encounters with the Stirling Numbers of the Second Kind
cites work: Adapting the directed grid theorem into an \textsf{FPT} algorithm
cites work: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Tour merging via branch-decomposition
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Parameterized Algorithms
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Fundamentals of parameterized complexity
cites work: Q4526990
cites work: Half-integral linkages in highly connected directed graphs
cites work: Q4598163
cites work: The directed subgraph homeomorphism problem
cites work: The Directed Flat Wall Theorem
cites work: Directed tree-width
cites work: Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
cites work: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
cites work: The Directed Grid Theorem
cites work: Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
cites work: Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
cites work: Introducing directed tree width
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Finding k Disjoint Paths in a Directed Planar Graph
cites work: Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
cites work: Highly connected non-2-linked digraphs
DOI: 10.1016/J.TCS.2021.10.023
description: scientific article; zbMATH DE number 7437226