Fixed-parameter tractability of multicut parameterized by the size of the cutset
From MaRDI portal
Publication:5419117
DOI10.1145/1993636.1993699zbMath1288.05283OpenAlexW2106959995MaRDI QIDQ5419117
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.713.4185
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (28)
On Multiway Cut Parameterized above Lower Bounds ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Dealing with several parameterized problems by random methods ⋮ Cluster Editing ⋮ Clique Cover and Graph Separation ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Unnamed Item ⋮ A kernel of order \(2k-c\log k\) for vertex cover ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Restricted vertex multicut on permutation graphs ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Confronting intractability via parameters ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Clustering with Local Restrictions ⋮ Fixed-Parameter Algorithms for Finding Agreement Supertrees ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Important Separators and Parameterized Algorithms ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems ⋮ Randomized fixed-parameter algorithms for the closest string problem
This page was built for publication: Fixed-parameter tractability of multicut parameterized by the size of the cutset
