On the parameterized complexity of separating certain sources from the target

DOI10.1016/J.TCS.2019.06.011MaRDI QIDQ2330108zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Bergé, Arpad Rimmel, Joanna Tomasik

Publication date 18 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.06.011

zbMATH Keywords

fixed-parameter tractabilitymulticutW[1-hardness]

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset

Cites work

• \textsc{Multicut} is FPT
• An improved parameterized algorithm for the minimum node multiway cut problem
• Approximating the k-multicut problem
• Computing small partial coverings
• Cutting up is hard to do: the parameterised complexity of k-cut and related problems
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 5032352 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Maximal Flow Through a Network
• Multiway cuts in node weighted graphs
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Parameterized graph separation problems
• Partial multicuts in trees
• The Complexity of Multiterminal Cuts

This page was built for publication: On the parameterized complexity of separating certain sources from the target

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