Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
DOI10.1016/J.TCS.2019.12.015zbMATH Open1436.68221OpenAlexW2995983675WikidataQ126587241 ScholiaQ126587241MaRDI QIDQ2290633FDOQ2290633
Authors: Cédric Bentz, Pierre Le Bodic 
Publication date: 29 January 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.12.015
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
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)
Cites Work
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Easy problems for tree-decomposable graphs
- The Complexity of Multiterminal Cuts
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Minimal multicut and maximal integer multiflow: a survey
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Treewidth. Computations and approximations
- On the hardness of approximating Multicut and Sparsest-Cut
- A logical approach to multicut problems
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Title not available (Why is that?)
- On the multiway cut polyhedron
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- \textsc{Multicut} is FPT
- A unified approach to approximating partial covering problems
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Title not available (Why is that?)
- Approximation schemes for a class of subset selection problems
- Approximating the k-multicut problem
- Lagrangian relaxation and partial cover (Extended abstract)
- Multiway cut and integer flow problems in trees
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Multicuts and integral multiflows in rings
- Title not available (Why is that?)
- Partial multicuts in trees
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
- Multicut algorithms via tree decompositions
- Partial vertex cover and budgeted maximum coverage in bipartite graphs
Cited In (8)
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Parameterized complexity dichotomy for Steiner Multicut
- 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
- SOFSEM 2006: Theory and Practice of Computer Science
- An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
- Title not available (Why is that?)
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
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)
