Improved parameterized and exact algorithms for cut problems on trees

doi:10.1016/j.tcs.2015.06.010

CORC > 北京大学 > 信息科学技术学院

	Improved parameterized and exact algorithms for cut problems on trees
	Kanj, Iyad ; Lin, Guohui ; Liu, Tian ; Tong, Weitian ; Xia, Ge ; Xu, Jinhui ; Yang, Boting ; Zhang, Fenghui ; Zhang, Peng ; Zhu, Binhai
刊名	THEORETICAL COMPUTER SCIENCE
	2015
关键词	Multicut Multiway cut Tree Parameterized algorithm Exact algorithm VERTEX COVER MULTIWAY CUT MULTICUT APPROXIMATE FLOW
DOI	10.1016/j.tcs.2015.06.010
英文摘要	We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O(rho(k)), where rho = root root 2 + 1 < 1.554 is the positive root of the polynomial x(4) - 2x(2) - 1. This improves the current-best algorithm of Chen et al. that runs in time O(1.619(k)). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O*(rho(k)). (C) 2015 Elsevier B.V. All rights reserved.; NSERC [RGPIN-2013-261290]; AITF; State Scholarship Fund of China; Natural Science Foundation of Shandong Province [ZR2012FZ002, ZR2013FM030]; Fundamental Research Funds of Shandong University [2015JC006]; SCI(E); EI; ARTICLE; ikanj@cs.depaul.edu; guohui@ualberta.ca; lt@pku.edu.cn; weitian@ualberta.ca; xiag@lafayette.edu; jinhui@buffalo.edu; boting@cs.uregina.ca; fhzhang@gmail.com; algzhang@sdu.edu.cn; bhz@cs.montana.edu; ,SI; 455-470; 607
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/439219]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Kanj, Iyad,Lin, Guohui,Liu, Tian,et al. Improved parameterized and exact algorithms for cut problems on trees[J]. THEORETICAL COMPUTER SCIENCE,2015.
APA	Kanj, Iyad.,Lin, Guohui.,Liu, Tian.,Tong, Weitian.,Xia, Ge.,...&Zhu, Binhai.(2015).Improved parameterized and exact algorithms for cut problems on trees.THEORETICAL COMPUTER SCIENCE.
MLA	Kanj, Iyad,et al."Improved parameterized and exact algorithms for cut problems on trees".THEORETICAL COMPUTER SCIENCE (2015).