Geodesic
A note on the computational complexity of hierarchical overlapping clustering
Applications of Mathematics, Tome 30 (1985) no. 6, pp. 453-460
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper the computational complexity of the problem of the approximation of a given dissimilarity measure on a finite set $X$ by a $k$-ultrametric on $X$ and by a Robinson dissimilarity measure on $X$ is investigared. It is shown that the underlying decision problems are NP-complete.
In this paper the computational complexity of the problem of the approximation of a given dissimilarity measure on a finite set $X$ by a $k$-ultrametric on $X$ and by a Robinson dissimilarity measure on $X$ is investigared. It is shown that the underlying decision problems are NP-complete.
DOI : 10.21136/AM.1985.104174
Classification : 03D15, 62H30, 68Q25, 68T10
Keywords: hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; $k$-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete 
@article{10_21136_AM_1985_104174,
     author = {K\v{r}iv\'anek, Mirko},
     title = {A note on the computational complexity of hierarchical overlapping clustering},
     journal = {Applications of Mathematics},
     pages = {453--460},
     year = {1985},
     volume = {30},
     number = {6},
     doi = {10.21136/AM.1985.104174},
     mrnumber = {0813533},
     zbl = {0581.62052},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1985.104174/}
}
TY  - JOUR
AU  - Křivánek, Mirko
TI  - A note on the computational complexity of hierarchical overlapping clustering
JO  - Applications of Mathematics
PY  - 1985
SP  - 453
EP  - 460
VL  - 30
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1985.104174/
DO  - 10.21136/AM.1985.104174
LA  - en
ID  - 10_21136_AM_1985_104174
ER  - 
%0 Journal Article
%A Křivánek, Mirko
%T A note on the computational complexity of hierarchical overlapping clustering
%J Applications of Mathematics
%D 1985
%P 453-460
%V 30
%N 6
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1985.104174/
%R 10.21136/AM.1985.104174
%G en
%F 10_21136_AM_1985_104174
Křivánek, Mirko. A note on the computational complexity of hierarchical overlapping clustering. Applications of Mathematics, Tome 30 (1985) no. 6, pp. 453-460. doi: 10.21136/AM.1985.104174

[1] E. Diday: Une représentation visuelle des classes empiétantes - les pyramides. Rap. de Recherche No 291, INRIA, Rocquencourt, 1984.

[2] M. R. Garey, D. S. Johnson: Computers and Intractability: a Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco, 1979. | MR | Zbl

[3] L. Hubert: A set-theoretical approach to the problem of hierarchical clustering. Journal of Mathematical Psychology, 15 (1977), 1 pp. 70--88. | DOI | MR | Zbl

[4] N. Jardine, R. Sibson: Mathematical Taxonomy. Wiley, London, 1971. | MR | Zbl

[5] R. M. Karp: Red liability among combinatorial problems. Complexity of computer computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. | MR

[6] M. Křivánek, J. Morávek: On NP-hardness in hierarchical clustering. COMPSTAT 1984, Proceedings, Physica-Verlag 1984. Editors: T. Havránek, Z. Šidák, M. Novák. | MR

Cité par Sources :