Improved parameterized and exact algorithms for cut problems on trees

DOI10.1016/J.TCS.2015.06.010MaRDI QIDQ896125zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

exact algorithmparameterized algorithmmulticutmultiway cut

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• A tight lower bound for planar multiway cut with fixed number of terminals
• Algorithms for cut problems on trees
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Fixed-parameter tractability and data reduction for multicut in trees
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Minimal multicut and maximal integer multiflow: a survey
• Multicut in trees viewed through the eyes of vertex cover
• Multiway cut and integer flow problems in trees
• On the generalized multiway cut in trees problem
• On the multiway cut polyhedron
• Parameterized graph separation problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• The Complexity of Multiterminal Cuts
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex cover: Further observations and further improvements
• \textsc{Multicut} is FPT

Cited in

(15)

• Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
• Multicut in trees viewed through the eyes of vertex cover
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Multicut algorithms via tree decompositions
• Optimal cuts and partitions in tree metrics in polynomial time
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• FPTAS’s for Some Cut Problems in Weighted Trees
• 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
• Algorithms for cut problems on trees
• An improved parameterized algorithm for the minimum node multiway cut problem
• Simple and improved parameterized algorithms for multiterminal cuts
• Multicut in trees viewed through the eyes of vertex cover

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)