An improved parameterized algorithm for the minimum node multiway cut problem

DOI10.1007/S00453-007-9130-6zbMATH Open1194.68168OpenAlexW2086937160MaRDI QIDQ2391180FDOQ2391180

Authors: Yang Liu, Songjian Lu, Jianer 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

Recommendations

• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• On multiway cut parameterized above lower bounds
• An improved parameterized algorithm for the multicut problem
• Algorithms for cut problems on trees
• Improved parameterized and exact algorithms for cut problems on trees

zbMATH Keywords

network flowfixed-parameter tractabilityminimum cutparameterized algorithmmultiway cut problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Parameterized graph separation problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Title not available (Why is that?)
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Title not available (Why is that?)
• Title not available (Why is that?)
• An improved approximation algorithm of MULTIWAY CUT.
• A 2-approximation algorithm for the directed multiway cut problem

Cited In (44)

• Balanced judicious bipartition is fixed-parameter tractable
• A faster FPT algorithm for bipartite contraction
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Parameterized algorithms for zero extension and metric labelling problems
• On the parameterized complexity of separating certain sources from the target
• Designing FPT algorithms for cut problems using randomized contractions
• FPT algorithms for path-transversal and cycle-transversal problems
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
• Quick separation in chordal and split graphs
• Parameterized tractability of multiway cut with parity constraints
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• The multi-terminal vertex separator problem: polytope characterization and TDI-ness
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• A faster parameterized algorithm for Group Feedback Edge Set
• Linear time parameterized algorithms for subset feedback vertex set
• An improved approximation algorithm of MULTIWAY CUT.
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• On multiway cut parameterized above lower bounds
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Odd cycle transversal in mixed graphs
• How to Cut a Graph into Many Pieces
• An improved fixed-parameter algorithm for max-cut parameterized by crossing number
• Multicut Is FPT
• On the parameterized complexity of finding separators with non-hereditary properties
• Deletion to scattered graph classes. I: Case of finite number of graph classes
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• An improved parameterized algorithm for treewidth
• Brief announcement: Bounded-degree cut is fixed-parameter tractable
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Faster exact algorithms for some terminal set problems
• The critical node detection problem in networks: a survey
• Minimum Bisection Is Fixed-Parameter Tractable
• Clique Cover and Graph Separation
• On the generalized multiway cut in trees problem
• Parameterized complexity of critical node cuts
• Hitting selected (odd) cycles
• Title not available (Why is that?)
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows

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

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