On structural parameterizations of the edge disjoint paths problem
From MaRDI portal
Publication:2032342
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
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
