On structural parameterizations of the edge disjoint paths problem

DOI10.1007/S00453-020-00795-3MaRDI QIDQ2032342zbMATH OpenOpenAlexFDO

Authors Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan

Publication date 11 June 2021

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

treewidthparameterized complexityfeedback vertex setedge disjoint path problemfracture number

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7278041
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• On the complexity of the planar directed edge-disjoint paths problem
• Edge-disjoint paths revisited
• scientific article; zbMATH DE number 2079393
• The power of cut-based parameters for computing edge-disjoint paths
• NP-completeness of some edge-disjoint paths problems

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A \(c^k n\) 5-approximation algorithm for treewidth
• A logical approach to multicut problems
• An application of simultaneous diophantine approximation in combinatorial optimization
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Approximating disjoint-path problems using packing integer programs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Finding edge-disjoint paths in partial \(k\)-trees
• Fundamentals of parameterized complexity
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• NP-completeness of some edge-disjoint paths problems
• New algorithms for maximum disjoint paths based on tree-likeness
• On routing disjoint paths in bounded treewidth graphs
• On structural parameterizations of the bounded-degree vertex deletion problem
• On the Computational Complexity of Combinatorial Problems
• Parameterized algorithms
• Parametrized complexity theory.
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• The power of cut-based parameters for computing edge disjoint paths
• Treewidth. Computations and approximations

Cited in

(12)

• scientific article; zbMATH DE number 7278041 (Why is no real title available?)
• Slim tree-cut width
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Hedonic diversity games: a complexity picture with more than two colors
• Group activity selection with few agent types
• The power of cut-based parameters for computing edge disjoint paths
• Edge-treewidth: algorithmic and combinatorial properties
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• The power of cut-based parameters for computing edge-disjoint paths
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• An O(log(N)) Algorithm View: Reliability Evaluation of Folded-crossed Hypercube in Terms of h-extra Edge-connectivity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032342)