An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

DOI10.1007/978-3-540-73951-7_43zbMATH Open1209.68615OpenAlexW1604791202MaRDI QIDQ3603552FDOQ3603552

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

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

Mathematics Subject Classification ID

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

Cited In (19)

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

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)