Title :
Correlation k-Clustering in Trees and Trees of Rings
Author :
Xiao, Xin ; Shuguang, Li
Author_Institution :
Coll. of Foreign Studies, Shandong Inst. of Bus. & Technol., Yantai, China
Abstract :
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.
Keywords :
graphs; optimisation; pattern clustering; polynomials; trees (mathematics); NP-complete; correlation k-clustering; cut negative edge; graphs; polynomial time exact algorithm; real-valued edge weight; trees of rings; uncut positive edge; Approximation algorithms; Clustering algorithms; Computer science; Educational institutions; Extraterrestrial measurements; NP-complete problem; Partitioning algorithms; Polynomials; Tree graphs; algorithms; correlation k-clustering; rings; trees; trees of rings;
Conference_Titel :
Information Engineering, 2009. ICIE '09. WASE International Conference on
Conference_Location :
Taiyuan, Shanxi
Print_ISBN :
978-0-7695-3679-8
DOI :
10.1109/ICIE.2009.245
