scientific article; zbMATH DE number 7278041

DOI10.4230/LIPICS.ISAAC.2017.36zbMATH Open1457.68215arXiv1711.02076MaRDI QIDQ5136255FDOQ5136255

Authors: Robert Ganian, Sebastian Ordyniak, Ramanujan Sridharan 

Publication date: 25 November 2020

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

Title of this publication is not available (Why is that?)

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph minors. XIII: The disjoint paths problem
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• Parameterized Algorithms
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Treewidth. Computations and approximations
• A logical approach to multicut problems
• On the Computational Complexity of Combinatorial Problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• NP-completeness of some edge-disjoint paths problems
• Finding edge-disjoint paths in partial \(k\)-trees
• Title not available (Why is that?)
• Approximating disjoint-path problems using packing integer programs
• A \(c^k n\) 5-approximation algorithm for treewidth
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
• On Routing Disjoint Paths in Bounded Treewidth Graphs

Cited In (5)

• On structural parameterizations of the edge disjoint paths problem
• 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
• Title not available (Why is that?)

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)