Multi-Multiway Cuts with Edge Labels

摘要：

We consider a natural generalization of both the multi-multiway cut and correlation clustering problems: the problem of multi-multiway cut with edge labels. The input to the problem is an undirected graph G=(V, E) with real nonnegative edge weights and k sets S1, S2, …, Sk of vertices, where each edge (u, v) is labeled either + or – depending on whether u and v have been deemed to be similar or dissimilar. The goal is to partition the vertices of G into clusters to minimize the total weight of cut + edges and uncut – edges, with the restriction that every pair of vertices u, v ∈ Si for some i must be in different clusters. We present an O(nlogn)-approximation algorithm for this problem, where n is the number of vertices of G.

关键词： approzimation algorithms correlation clustering minimum multicut minimum multiway cut

作者: Li Shuguang Xin Xiao

作者单位: College of Computer Science and Technology Shandong Institute of Business and Technology Yantai, Chi College of Foreign Studies Shandong Institute of Business and Technology Yantai, China

会议类型: 国际会议

会议名称: 第四届国际计算机新科技与教育学术会议(2009 4th International Conference on Computer Science & Education)

会议地点: 南京

会议语种:英文

页码: 1860-1863

在线出版日期: 2009-07-25（万方平台首次上网日期，不代表论文的发表时间）