Algorithms for cut problems on trees

DOI10.1007/978-3-319-12691-3_22MaRDI QIDQ2942406zbMATH OpenOpenAlexFDO

Authors Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu, Iyad Kanj

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3653

zbMATH Keywords

multicut on trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the {sc multicut on trees} and the {sc generalized multiway Cut on trees} problems. For the {sc multicut on trees} problem, we present a parameterized algorithm that runs in time $O^{\ast }(h{o}^k)$, where $ho=sqrtsqrt2+1approx1.555$ is the positive root of the polynomial $x^4-2x^2-1$. This improves the current-best algorithm of Chen et al. that runs in time $O^{\ast }(1.619^k)$. For the {sc generalized multiway cut on trees} problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the {sc generalized multiway cut on trees} problem to the {sc multicut on trees} problem, our results give a parameterized algorithm that solves the {sc generalized multiway cut on trees} problem in time $O^{\ast }(h{o}^k)$, where $ho=sqrtsqrt2+1approx1.555$ time.

Recommendations

• Improved parameterized and exact algorithms for cut problems on trees
• On the generalized multiway cut in trees problem
• On the generalized multiway cut in trees problem
• Multicut in trees viewed through the eyes of vertex cover
• Fixed-parameter tractability and data reduction for multicut in trees

Cited in

(16)

• On weighted multiway cuts in trees
• An improved parameterized algorithm for the minimum node multiway cut problem
• On the generalized multiway cut in trees problem
• An \(O ^{*}(1.84^{k })\) parameterized algorithm for the multiterminal cut problem
• Algorithms Solving the Matching Cut Problem
• On the generalized multiway cut in trees problem
• Fixed-parameter tractability and data reduction for multicut in trees
• Multicut algorithms via tree decompositions
• FPTAS’s for Some Cut Problems in Weighted Trees
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Multicut in trees viewed through the eyes of vertex cover
• Multicut in trees viewed through the eyes of vertex cover
• Parameterized complexity of weighted multicut in trees
• Parameterized complexity of multicut in weighted trees
• Improved parameterized and exact algorithms for cut problems on trees

This page was built for publication: Algorithms for cut problems on trees

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