scientific article; zbMATH DE number 7278041

DOI10.4230/LIPICS.ISAAC.2017.36MaRDI QIDQ5136255zbMATH OpenFDO

Authors Robert Ganian, Sebastian Ordyniak, Ramanujan Sridharan

Publication date 25 November 2020

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

zbMATH Keywords

treewidthparameterized complexityfeedback vertex setfracture numberedge disjoint paths problem

Mathematics Subject Classification ID

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

Recommendations

• On structural parameterizations of the edge disjoint paths problem
• 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 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 minors. XIII: The disjoint paths problem
• Integer Programming with a Fixed Number of Variables
• 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 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
• Treewidth. Computations and approximations

Cited in

(6)

• On structural parameterizations of the edge disjoint paths problem
• The power of cut-based parameters for computing edge disjoint paths
• The power of cut-based parameters for computing edge-disjoint paths
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• The complexity of optimizing atomic congestion
• scientific article; zbMATH DE number 7525485 (Why is no real title available?)

This page was built for publication:

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