标题:A New Approximation Algorithm for the Unbalanced Min s-t Cut Problem
作者:Zhang, Peng
通讯作者:Zhang, P
作者机构:[Zhang, P]Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
会议名称:20th International Conference on Computing and Combinatorics (COCOON)
会议日期:AUG 04-06, 2014
来源:COMPUTING AND COMBINATORICS, COCOON 2014
出版年:2014
卷:8591
页码:346-356
摘要:Let k be an input parameter. An s-t cut is of k-size if its s-side has size at most k. The Min k-Size s-t Cut problem asks to find a k-size s-t cut with the minimum capacity. Being the unbalanced version of the famous Min s-t Cut problem, this problem is fundamental and has extensive applications, especially in community identification in social and information networks. In this paper, we give a new k+1/k+1-k*-approximation algorithm for the Min k-Size s-t Cut problem, where k* is the size of s-side of an optimal solution.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:1
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84904737299&doi=10.1007%2f978-3-319-08783-2_30&partnerID=40&md5=d0e961183d33a6f863ee7bdc288903d1
TOP