Multicut is FPT
From MaRDI portal
Publication:5419116
DOI10.1145/1993636.1993698zbMath1288.05264MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Multicut Is FPT, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Fixed-Parameter Algorithms for Finding Agreement Supertrees, Cluster Editing, Hitting Selected (Odd) Cycles, Unnamed Item, Unnamed Item, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, The complexity of multicut and mixed multicut problems in (di)graphs, Multicut in trees viewed through the eyes of vertex cover, Restricted vertex multicut on permutation graphs, Confronting intractability via parameters, On the parameterized complexity of finding separators with non-hereditary properties, Parameterized complexity of critical node cuts, Improved parameterized and exact algorithms for cut problems on trees, An FPT algorithm for planar multicuts with sources and sinks on the outer face, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, On the parameterized complexity of separating certain sources from the target, Linear kernels for separating a graph into components of bounded size, Multicuts in planar and bounded-genus graphs with bounded number of terminals, On the generalized multiway cut in trees problem, An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem, 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, Clique Cover and Graph Separation, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, Important Separators and Parameterized Algorithms, Designing FPT Algorithms for Cut Problems Using Randomized Contractions
