Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
From MaRDI portal
(Redirected from Publication:2290633)
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
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- SOFSEM 2006: Theory and Practice of Computer Science
- scientific article; zbMATH DE number 1187148
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
Cites work
- scientific article; zbMATH DE number 3876616 (Why is no real title available?)
- scientific article; zbMATH DE number 3705908 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 2079369 (Why is no real title available?)
- A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
- A logical approach to multicut problems
- A unified approach to approximating partial covering problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximating the k-multicut problem
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation schemes for a class of subset selection problems
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Easy problems for tree-decomposable graphs
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Graph minors. II. Algorithmic aspects of tree-width
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- Lagrangian relaxation and partial cover (Extended abstract)
- Minimal multicut and maximal integer multiflow: a survey
- Multicut algorithms via tree decompositions
- Multicuts and integral multiflows in rings
- Multiway cut and integer flow problems in trees
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- On the hardness of approximating Multicut and Sparsest-Cut
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- On the multiway cut polyhedron
- Partial multicuts in trees
- Partial vertex cover and budgeted maximum coverage in bipartite graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- The Complexity of Multiterminal Cuts
- Treewidth. Computations and approximations
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- \textsc{Multicut} is FPT
Cited in
(8)- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- SOFSEM 2006: Theory and Practice of Computer Science
- Parameterized complexity dichotomy for Steiner Multicut
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
- An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- scientific article; zbMATH DE number 1187148 (Why is no real title available?)
This page was built for publication: Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290633)
