On the complexity of the multicut problem in bounded tree-width graphs and digraphs
From MaRDI portal
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Recommendations
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- Multicuts in unweighted digraphs with bounded degree and bounded tree-width
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- scientific article; zbMATH DE number 1187148
- Multi-multiway cut problem on graphs of bounded branch width
- Multicut on graphs of bounded clique-width
- On algorithms employing treewidth for \(L\)-bounded cut problems
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- The complexity of multicut and mixed multicut problems in (di)graphs
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2079369 (Why is no real title available?)
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximation Algorithms for Steiner and Directed Multicuts
- Directed tree-width
- Graph minors. II. Algorithmic aspects of tree-width
- Hardness of cut problems in directed graphs
- Minimal multicut and maximal integer multiflow: a survey
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- On the Max-flow min-cut ratio for directed multicommodity flows
- On the hardness of approximating Multicut and Sparsest-Cut
- Optimization, approximation, and complexity classes
- Primal-dual approximation algorithms for integral flow and multicut in trees
- SOFSEM 2006: Theory and Practice of Computer Science
- The Complexity of Multiterminal Cuts
Cited in
(17)- Multicuts in unweighted digraphs with bounded degree and bounded tree-width
- New results on planar and directed multicuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Multicut on graphs of bounded clique-width
- The complexity of multicut and mixed multicut problems in (di)graphs
- SOFSEM 2006: Theory and Practice of Computer Science
- An approximation algorithm for the generalized \(k\)-multicut problem
- A simple algorithm for multicuts in planar graphs with outer terminals
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- Multi-multiway cut problem on graphs of bounded branch width
- Disjoint paths in sparse graphs
- An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
- An FPT algorithm for planar multicuts with sources and sinks on the outer face
- scientific article; zbMATH DE number 1187148 (Why is no real title available?)
This page was built for publication: On the complexity of the multicut problem in bounded tree-width graphs and digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q944745)
