DocumentCode
498530
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
Volume
1
fYear
2009
fDate
10-11 July 2009
Firstpage
217
Lastpage
220
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Engineering, 2009. ICIE '09. WASE International Conference on
Conference_Location
Taiyuan, Shanxi
Print_ISBN
978-0-7695-3679-8
Type
conf
DOI
10.1109/ICIE.2009.245
Filename
5210924
Link To Document