Improved parameterized and exact algorithms for cut problems on trees
DOI10.1016/J.TCS.2015.06.010zbMATH Open1333.05293OpenAlexW571512295MaRDI QIDQ896125FDOQ896125
Authors: Iyad Kanj, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu, Guohui 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
Recommendations
- Algorithms for cut problems on trees
- Improved algorithms for the multicut and multiflow problems in rooted trees
- On algorithms employing treewidth for \(L\)-bounded cut problems
- Efficient algorithms for generalized cut‐trees
- An improved parameterized algorithm for the multicut problem
- Simple and improved parameterized algorithms for multiterminal cuts
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- Optimal cuts and partitions in tree metrics in polynomial time
- On the generalized multiway cut in trees problem
- On the generalized multiway cut in trees problem
Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The Complexity of Multiterminal Cuts
- Title not available (Why is that?)
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Title not available (Why is that?)
- Minimal multicut and maximal integer multiflow: a survey
- Parameterized graph separation problems
- Title not available (Why is that?)
- Fixed-parameter tractability and data reduction for multicut in trees
- On the multiway cut polyhedron
- Multicut in trees viewed through the eyes of vertex cover
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- \textsc{Multicut} is FPT
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Vertex cover: Further observations and further improvements
- Multiway cut and integer flow problems in trees
- A tight lower bound for planar multiway cut with fixed number of terminals
- On the generalized multiway cut in trees problem
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- Algorithms for cut problems on trees
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
Cited In (15)
- Optimal cuts and partitions in tree metrics in polynomial time
- FPTAS’s for Some Cut Problems in Weighted Trees
- Multicut in trees viewed through the eyes of vertex cover
- Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
- Simple and improved parameterized algorithms for multiterminal cuts
- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
- Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Algorithms for cut problems on trees
- An improved parameterized algorithm for the minimum node multiway cut problem
- Multicut in trees viewed through the eyes of vertex cover
- Multicut algorithms via tree decompositions
- On the generalized multiway cut in trees problem
- On the generalized multiway cut in trees problem
- Fixed-parameter tractability and data reduction for multicut in trees
This page was built for publication: Improved parameterized and exact 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 Q896125)
