A note on the computational complexity of hierarchical overlapping clustering
Applications of Mathematics, Tome 30 (1985) no. 6, pp. 453-460.

Voir la notice de l'article dans Czech Digital Mathematics Library

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
Mots-clés : 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},
     publisher = {mathdoc},
     volume = {30},
     number = {6},
     year = {1985},
     doi = {10.21136/AM.1985.104174},
     mrnumber = {0813533},
     zbl = {0581.62052},
     language = {en},
     url = {https://geodesic-test.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
PB  - mathdoc
UR  - https://geodesic-test.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
%I mathdoc
%U https://geodesic-test.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. https://geodesic-test.mathdoc.fr/articles/10.21136/AM.1985.104174/

Cité par Sources :