The power of cut-based parameters for computing edge-disjoint paths
From MaRDI portal
Publication:2659778
DOI10.1007/S00453-020-00772-WOpenAlexW2975202594MaRDI QIDQ2659778FDOQ2659778
Authors: Robert Ganian, Sebastian Ordyniak 
Publication date: 26 March 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00772-w
Recommendations
Cites Work
- Graph theory
- Fundamentals of parameterized complexity
- Graph minors. XIII: The disjoint paths problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Parametrized complexity theory.
- Parameterized algorithms
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- On the Computational Complexity of Combinatorial Problems
- Improved bounds on Bell numbers and on moments of sums of random variables
- The structure of graphs not admitting a fixed immersion
- Immersions in highly edge connected graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Finding edge-disjoint paths in partial \(k\)-trees
- Title not available (Why is that?)
- Approximating disjoint-path problems using packing integer programs
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- On structural parameterizations of the bounded-degree vertex deletion problem
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- Algorithmic applications of tree-cut width
- Linear kernels for edge deletion problems to immersion-closed graph classes
- New algorithms for maximum disjoint paths based on tree-likeness
- On routing disjoint paths in bounded treewidth graphs
- Title not available (Why is that?)
Cited In (11)
- Algorithmic applications of tree-cut width
- Slim tree-cut width
- On structural parameterizations of the edge disjoint paths problem
- Edge-treewidth: algorithmic and combinatorial properties
- Fixed-parameter algorithms for computing RAC drawings of graphs
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- The power of cut-based parameters for computing edge disjoint paths
- Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
- The complexity of optimizing atomic congestion
- An O(log(N)) Algorithm View: Reliability Evaluation of Folded-crossed Hypercube in Terms of h-extra Edge-connectivity
- Title not available (Why is that?)
This page was built for publication: The power of cut-based parameters for computing edge-disjoint paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659778)
