Correlation k-Clustering in Trees and Trees of Rings
Xin Xiao, LI Shu-guang · 2009
We consider the following correlation k-clustering problem: given a graph with real-valued edge weights (both positive and negative), extend a k-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 ges 2. We present polynomial time exact algorithms for trees, rings and trees of rings.