Algorithms for Cut Problems on Trees

doi:10.1007/978-3-319-12691-3_22

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

	Algorithms for Cut Problems on Trees
	Kanj, Iyad ; Lin, Guohui ; Liu, Tian ; Tong, Weitian ; Xia, G. ; Xu, Jinhui ; Yang, Boting ; Zhang, Fenghui ; Zhang, Peng ; Zhu, Binhai
刊名	lecture notes in computer science including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics
	2014
DOI	10.1007/978-3-319-12691-3_22
英文摘要	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? (??k), where ?? = _ ?? 2 + 1 ?? 1.555 is the positive root of the polynomial x4 - 2x2 - 1. This improves the current-best algorithm of Chen et al. that runs in time O? (1.619k). By reducing generalized multiway cut on trees to multicut on trees, our results give a parameterized algorithm that solves the generalized multiway cut on trees problem in time O? (??k). We also show that the generalized multiway cut on trees problem is solvable in polynomial time if the number of terminal sets is a fixed constant. Springer International Publishing Switzerland 2014.; EI; CPCI-S(ISTP); 0; PROCEEDINGS PAPER; ikanj@cs.depaul.edu; guohui@ualberta.ca; lt@pku.edu.cn; weitiang@ualberta.ca; xiag@lafayette.edu; jinhui@buffalo.edu; boting@cs.uregina.ca; fhzhang@gmail.com; algzhang@sdu.edu.cn; bhz@cs.montana.edu; 283-298; 8881
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/327816]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Kanj, Iyad,Lin, Guohui,Liu, Tian,et al. Algorithms for Cut Problems on Trees[J]. lecture notes in computer science including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics,2014.
APA	Kanj, Iyad.,Lin, Guohui.,Liu, Tian.,Tong, Weitian.,Xia, G..,...&Zhu, Binhai.(2014).Algorithms for Cut Problems on Trees.lecture notes in computer science including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics.
MLA	Kanj, Iyad,et al."Algorithms for Cut Problems on Trees".lecture notes in computer science including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics (2014).