An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

DOI10.1007/978-3-540-73951-7_43MaRDI QIDQ3603552zbMATHOpenAlexFDO

Authors Yang Liu, Songjian Lu, Jianer Chen

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• An improved parameterized algorithm for the minimum node multiway cut problem
• An improved parameterized algorithm for the multicut problem
• Algorithms for cut problems on trees
• Improved parameterized and exact algorithms for cut problems on trees

Cited in

(19)

• An improved fixed-parameter algorithm for max-cut parameterized by crossing number
• Almost 2-SAT is fixed-parameter tractable
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Parameterized tractability of multiway cut with parity constraints
• An improved parameterized algorithm for the multicut problem
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• An improved approximation algorithm of MULTIWAY CUT.
• Parameterized complexity of multi-node hubs
• An improved parameterized algorithm for the minimum node multiway cut problem
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• Important separators and parameterized algorithms
• Simple and improved parameterized algorithms for multiterminal cuts
• What's next? Future directions in parameterized complexity
• Improved algorithms for feedback vertex set problems
• Clustering with Local Restrictions
• Parameterized algorithms for MIN-MAX multiway cut and List digraph homomorphism

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 Q3603552)