On structural parameterizations of the edge disjoint paths problem

DOI10.1007/s00453-020-00795-3OpenAlexW2963428363MaRDI QIDQ2032342

M. S. Ramanujan, Robert Ganian, Sebastian Ordyniak

Publication date: 11 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00795-3

zbMATH Keywords

treewidthfeedback vertex setparameterized complexityedge disjoint path problemfracture number

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (5)

Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Hedonic diversity games: a complexity picture with more than two colors ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ An O(log(N)) Algorithm View: Reliability Evaluation of Folded-crossed Hypercube in Terms of h-extra Edge-connectivity ⋮ Group activity selection with few agent types

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Primal-dual approximation algorithms for integral flow and multicut in trees
• On the computational complexity of vertex integrity and component order connectivity
• An application of simultaneous diophantine approximation in combinatorial optimization
• Treewidth. Computations and approximations
• Approximating disjoint-path problems using packing integer programs
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• Finding edge-disjoint paths in partial \(k\)-trees
• The power of cut-based parameters for computing edge disjoint paths
• A logical approach to multicut problems
• Parametrized complexity theory.
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Integer Programming with a Fixed Number of Variables
• On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
• Graph Layout Problems Parameterized by Vertex Cover
• Minkowski's Convex Body Theorem and Integer Programming
• On the Computational Complexity of Combinatorial Problems
• New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• On Routing Disjoint Paths in Bounded Treewidth Graphs
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: On structural parameterizations of the edge disjoint paths problem