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

DOI10.1007/S00453-020-00772-WMaRDI QIDQ2659778OpenAlexFDO

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

zbMATH Keywords

parameterized complexityedge-disjoint path problemtree-cut widthfeedback edge set

Mathematics Subject Classification ID

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

Recommendations

• The power of cut-based parameters for computing edge disjoint paths
• On structural parameterizations of the edge disjoint paths problem
• scientific article; zbMATH DE number 7278041
• Edge Disjoint Paths in Moderately Connected Graphs
• Edge Disjoint Paths in Moderately Connected Graphs

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 7278041 (Why is no real title available?)
• Algorithmic applications of tree-cut width
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Approximating disjoint-path problems using packing integer programs
• Finding edge-disjoint paths in partial \(k\)-trees
• Fundamentals of parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
• Graph theory
• Immersions in highly edge connected graphs
• Improved bounds on Bell numbers and on moments of sums of random variables
• Linear kernels for edge deletion problems to immersion-closed graph classes
• Linear time solvable optimization problems on graphs of bounded clique-width
• 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 structure of graphs not admitting a fixed immersion

Cited in

(11)

• An O(log(N)) Algorithm View: Reliability Evaluation of Folded-crossed Hypercube in Terms of h-extra Edge-connectivity
• Edge-treewidth: algorithmic and combinatorial properties
• On structural parameterizations of the edge disjoint paths problem
• Fixed-parameter algorithms for computing RAC drawings of graphs
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
• The power of cut-based parameters for computing edge disjoint paths
• scientific article; zbMATH DE number 7278041 (Why is no real title available?)
• Algorithmic applications of tree-cut width
• The complexity of optimizing atomic congestion
• Slim tree-cut width

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)