标题:A new approximation algorithm for the unbalanced Min s-t Cut problem
作者:Zhang, Peng
通讯作者:Zhang, Peng
作者机构:[Zhang, Peng] Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China.
会议名称:20th International Conference on Computing and Combinatorics (COCOON)
会议日期:AUG 04-06, 2014
来源:THEORETICAL COMPUTER SCIENCE
出版年:2016
卷:609
页码:658-665
DOI:10.1016/j.tcs.2015.02.040
关键词:Unbalanced cut; MM s-t cut; Approximation algorithm; Linear programming;; Network community
摘要:Being the unbalanced version of the famous Min s-t Cut problem, the Min k-Size s-t Cut problem asks to find a k-size s-t cut with the minimum capacity, where a k-size s-t cut means an s-t cut with its s-side having size at most k. This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k-Size s-t Cut problem is NP-hard and can be approximated within O (logn), where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k-Size s-t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k+1/K+1-k*, where k* is the size of the s-side of an optimal solution. (C) 2015 Elsevier B.V. All rights reserved.
收录类别:CPCI-S;EI;SCOPUS;SCIE
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84948822892&doi=10.1016%2fj.tcs.2015.02.040&partnerID=40&md5=635f6d6bf84c172ca37a3fb407f92b42
TOP