Parameterized complexity dichotomy for Steiner Multicut

DOI10.4230/LIPICS.STACS.2015.157zbMATH Open1355.68113MaRDI QIDQ2954992FDOQ2954992

Authors: Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen 

Publication date: 24 January 2017

Recommendations

• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• SOFSEM 2006: Theory and Practice of Computer Science

zbMATH Keywords

fixed-parameter tractabilitygraph cut problemsSteiner cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Designing FPT algorithms for cut problems using randomized contractions
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT

This page was built for publication: Parameterized complexity dichotomy for Steiner Multicut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954992)