Improved parameterized and exact algorithms for cut problems on trees
Publication:896125
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
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)
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
