标题: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
通讯作者:Xia, G
作者机构:[Kanj, Iyad] Depaul Univ, Sch Comp, Chicago, IL 60604 USA.; [Lin, Guohui; Tong, Weitian] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada.; 更多
会议名称:8th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
会议日期:DEC 19-21, 2014
来源:COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014)
出版年:2014
卷:8881
页码:283-298
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*(rho(k)), where rho = root root 2 + 1 approximate to 1.555 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)). 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*(rho(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.
收录类别:CPCI-S;EI;SCOPUS
Scopus被引频次:2
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84921496753&doi=10.1007%2f978-3-319-12691-3_22&partnerID=40&md5=1ef834b8832180dcd4eaa05606c3e596
TOP