Improved parameterized and exact algorithms for cut problems on trees

DOI10.1016/j.tcs.2015.06.010zbMath1333.05293OpenAlexW571512295MaRDI QIDQ896125

Weitian Tong, Iyad A. Kanj, Tian Liu, Ge Xia, Peng Zhang, Fenghui Zhang, Boting Yang, Jinhui Xu, Binhai Zhu, Guo-Hui Lin

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.010

zbMATH Keywords

exact algorithmparameterized algorithmmulticutmultiway cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Parameterized complexity and approximation issues for the colorful components problems ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multicut in trees viewed through the eyes of vertex cover
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Parameterized graph separation problems
• On the generalized multiway cut in trees problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex Cover: Further Observations and Further Improvements
• 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
• Algorithms for Cut Problems on Trees
• Fixed-parameter tractability and data reduction for multicut in trees
• Multiway cut and integer flow problems in trees
• On the multiway cut polyhedron
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset

This page was built for publication: Improved parameterized and exact algorithms for cut problems on trees