Polynomial algorithms for nested univariate clustering

被引：3
作者：
Hansen, P
Jaumard, B
Simeone, B
机构：
[1] Ecole Polytech, GERAD, Montreal, PQ H3T 1V6, Canada
[2] Ecole Polytech, Ecole Hautes Etud Commerciales, Montreal, PQ H3T 1V6, Canada
[3] Univ La Sapienza, Dept Stat, Rome, Italy
来源：
DISCRETE MATHEMATICS | 2002年 / 245卷 / 1-3期
基金：
加拿大自然科学与工程研究理事会;
关键词：
clustering; clique; polynomial algorithm;
D O I：
10.1016/S0012-365X(01)00135-2
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Clique partitioning in Euclidean space R-n consists in finding a partition of a given set of N points into M clusters in order to minimize the sum of within-cluster interpoint distances. For n = 1 clusters need not consist of consecutive points on a line but have a nestedness property. Exploiting this property, an O((NM2)-M-5) dynamic programming algorithm is proposed. A theta(N) algorithm is also given for the case M = 2. (C) 2002 Published by Elsevier Science B.V.
引用
收藏
页码：93 / 105
页数：13
相关论文
共 17 条
12