An improved parameterized algorithm for the minimum node multiway cut problem

DOI10.1007/s00453-007-9130-6zbMath1194.68168OpenAlexW2086937160MaRDI QIDQ2391180

Songjian Lu, Yang Liu, Jian'er Chen

Publication date: 24 July 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9130-6

zbMATH Keywords

minimum cutnetwork flowfixed-parameter tractabilityparameterized algorithmmultiway cut problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (37)

Faster exact algorithms for some terminal set problems ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Clique Cover and Graph Separation ⋮ Odd cycle transversal in mixed graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multicut Is FPT ⋮ Unnamed Item ⋮ On the generalized multiway cut in trees problem ⋮ Unnamed Item ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ A faster FPT algorithm for bipartite contraction ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ How to Cut a Graph into Many Pieces ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Quick separation in chordal and split graphs ⋮ The Multi-terminal Vertex Separator Problem: Polytope Characterization and TDI-ness ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized graph separation problems
• An improved approximation algorithm of MULTIWAY CUT.
• A 2-Approximation Algorithm for the Directed Multiway Cut Problem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• The Complexity of Multiterminal Cuts
• Fixed-Parameter Tractability and Completeness I: Basic Results

This page was built for publication: An improved parameterized algorithm for the minimum node multiway cut problem