scientific article; zbMATH DE number 7278041

DOI10.4230/LIPIcs.ISAAC.2017.36zbMath1457.68215arXiv1711.02076MaRDI QIDQ5136255

Robert Ganian, Ramanujan Sridharan, Sebastian Ordyniak

Publication date: 25 November 2020

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

treewidthfeedback vertex setparameterized complexityfracture numberedge disjoint paths problem

Mathematics Subject Classification ID

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

Related Items (2)

The power of cut-based parameters for computing edge-disjoint paths ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Primal-dual approximation algorithms for integral flow and multicut in trees
• 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
• 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 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: