A note on the computational complexity of hierarchical overlapping clustering
Aplikace matematiky (1985)
- Volume: 30, Issue: 6, page 453-460
- ISSN: 0862-7940
Access Full Article
top
Abstract
topHow to cite
topKřivánek, Mirko. "A note on the computational complexity of hierarchical overlapping clustering." Aplikace matematiky 30.6 (1985): 453-460. <http://eudml.org/doc/15427>.
@article{Křivánek1985,
abstract = {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.},
author = {Křivánek, Mirko},
journal = {Aplikace matematiky},
keywords = {hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; $k$-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete; hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; k-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete},
language = {eng},
number = {6},
pages = {453-460},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A note on the computational complexity of hierarchical overlapping clustering},
url = {http://eudml.org/doc/15427},
volume = {30},
year = {1985},
}
TY - JOUR
AU - Křivánek, Mirko
TI - A note on the computational complexity of hierarchical overlapping clustering
JO - Aplikace matematiky
PY - 1985
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 30
IS - 6
SP - 453
EP - 460
AB - 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.
LA - eng
KW - hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; $k$-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete; hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; k-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete
UR - http://eudml.org/doc/15427
ER -
References
top- E. Diday, Une représentation visuelle des classes empiétantes - les pyramides, Rap. de Recherche No 291, INRIA, Rocquencourt, 1984. (1984)
- M. R. Garey, D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979. (1979) Zbl0411.68039MR0519066
- L. Hubert, 10.1016/0022-2496(77)90041-4, Journal of Mathematical Psychology, 15 (1977), 1 pp. 70--88. (1977) Zbl0358.62042MR0527187DOI10.1016/0022-2496(77)90041-4
- N. Jardine, R. Sibson, Mathematical Taxonomy, Wiley, London, 1971. (1971) Zbl0322.62065MR0441395
- R. M. Karp, Red liability among combinatorial problems, Complexity of computer computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. (1972) MR0373375
- 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. (1984) MR0806995
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.