Correlation k-Clustering in Trees and Trees of Rings

摘要：

We consider the following correlation k-clustering problem: given a graph with real-valued edge weights (both positive and negative), extend a A-clustering of some vertices to partition all the vertices into clusters so as to maximize the total absolute weight of cut negative edges and uncut positive edges. This problem for general graphs is NP-complete for all fixed k≥2. We present polynomial time exact algorithms for trees, rings and trees of rings.

关键词： algorithms correlation k-clustering trees rings trees of rings

作者: Xin Xiao Li Shuguang

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

会议类型: 国际会议

会议名称: 2009 WASE International Conference on Information Engineering(2009年国际信息工程会议)(ICIE 2009)

会议地点: 太原

会议语种:英文

页码: 217-220

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