Correlation k-clustering with pre-clustered items on cactus graphs
LI Shu-guang, Xin Xiao · 2010
Given a graph G = (V, E) with real-valued edge weights, the problem of correlation k-clustering with pre-clustered items is to extend a k-clustering of distinguished vertices of G (pre-clustered items) to partition all the vertices into clusters so as to minimize the total absolute weight of cut positive edges and uncut negative edges. This problem for general graphs is APX-complete. A polynomial time exact algorithm for cactus graphs is presented.