Multicut is FPT
From MaRDI portal
Publication:5419116
DOI10.1145/1993636.1993698zbMath1288.05264OpenAlexW2082223143MaRDI QIDQ5419116
Jean Daligault, Nicolas Bousquet, Steéphan Thomassé
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: https://doi.org/10.1145/1993636.1993698
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (29)
Linear kernels for separating a graph into components of bounded size ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Cluster Editing ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Clique Cover and Graph Separation ⋮ The complexity of multicut and mixed multicut problems in (di)graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Multicut Is FPT ⋮ On the generalized multiway cut in trees problem ⋮ 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 ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Parameterized complexity of critical node cuts ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ 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
This page was built for publication: Multicut is FPT
