Improved parameterized and exact algorithms for cut problems on trees
type: Item
instance of: scholarly article
title: Improved parameterized and exact algorithms for cut problems on trees
zbMATH Open document ID: 1333.05293
author: Iyad Kanj
author: Tian Liu
author: Weitian Tong
author: Ge Xia
author: Jinhui Xu
author: Boting Yang
author: Fenghui Zhang
author: Peng Zhang
author: Binhai Zhu
author: Guohui Lin
published in: Theoretical Computer Science
publication date: 2015-12-11T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6520522
zbMATH Keywords: multicut
zbMATH Keywords: multiway cut
zbMATH Keywords: parameterized algorithm
zbMATH Keywords: exact algorithm
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.06.010
OpenAlex ID: W571512295
cites work: Multicut is FPT
cites work: A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
cites work: Multicut in trees viewed through the eyes of vertex cover
cites work: Vertex cover: Further observations and further improvements
cites work: Q5743512
cites work: On the multiway cut polyhedron
cites work: Multiway cut and integer flow problems in trees
cites work: Minimal multicut and maximal integer multiflow: a survey
cites work: The Complexity of Multiterminal Cuts
cites work: Q4393480
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Fixed-parameter tractability and data reduction for multicut in trees
cites work: Algorithms for Cut Problems on Trees
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
cites work: On the generalized multiway cut in trees problem
cites work: Parameterized graph separation problems
cites work: A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
cites work: Fixed-parameter tractability of multicut parameterized by the size of the cutset
cites work: Q5710169
cites work: Q4869540
DOI: 10.1016/J.TCS.2015.06.010
Recommended article: Algorithms for Cut Problems on Trees
Recommended article: Improved algorithms for the multicut and multiflow problems in rooted trees
Recommended article: On Algorithms Employing Treewidth for $L$-bounded Cut Problems
Recommended article: Efficient algorithms for generalized cut‐trees
Recommended article: Q3014297
Recommended article: Simple and improved parameterized algorithms for multiterminal cuts
Recommended article: Solving cut-problems in quadratic time for graphs with bounded treewidth
Recommended article: Optimal cuts and partitions in tree metrics in polynomial time
Recommended article: On the generalized multiway cut in trees problem
Recommended article: On the Generalized Multiway Cut in Trees Problem
description: scientific article; zbMATH DE number 6520522