An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
From MaRDI portal
Publication:2445900
DOI10.1016/j.ipl.2013.12.001zbMath1302.68210arXiv1711.06397OpenAlexW2092029376MaRDI QIDQ2445900
Yixin Cao, Jian'er Chen, Jia-Hao Fan
Publication date: 15 April 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.06397
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (5)
Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Parameterized complexity of happy coloring problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Edge bipartization faster than \(2^k\) ⋮ Parameterized complexity of critical node cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized graph separation problems
- Simple and improved parameterized algorithms for multiterminal cuts
- An improved parameterized algorithm for the minimum node multiway cut problem
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- On Multiway Cut Parameterized above Lower Bounds
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Algorithmic Aspects of Graph Connectivity
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Multicut is FPT
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Approximation Algorithms for Submodular Multiway Partition
- Simplex partitioning via exponential clocks and the multiway cut problem
This page was built for publication: An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
