| Title:
|
A note on the computational complexity of hierarchical overlapping clustering (English) |
| Author:
|
Křivánek, Mirko |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
30 |
| Issue:
|
6 |
| Year:
|
1985 |
| Pages:
|
453-460 |
| Summary lang:
|
English |
| Summary lang:
|
Czech |
| Summary lang:
|
Russian |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
hierarchical overlapping clustering |
| Keyword:
|
computational complexity |
| Keyword:
|
approximation of a given dissimilarity measure |
| Keyword:
|
$k$-ultrametric |
| Keyword:
|
Robinson dissimilarity measure |
| Keyword:
|
decision problems |
| Keyword:
|
NP-complete |
| MSC:
|
03D15 |
| MSC:
|
62H30 |
| MSC:
|
68Q25 |
| MSC:
|
68T10 |
| idZBL:
|
Zbl 0581.62052 |
| idMR:
|
MR0813533 |
| DOI:
|
10.21136/AM.1985.104174 |
| . |
| Date available:
|
2008-05-20T18:28:53Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/104174 |
| . |
| Reference:
|
[1] E. Diday: Une représentation visuelle des classes empiétantes - les pyramides.Rap. de Recherche No 291, INRIA, Rocquencourt, 1984. |
| Reference:
|
[2] M. R. Garey, D. S. Johnson: Computers and Intractability: a Guide to the Theory of NP-completeness.W. H. Freeman, San Francisco, 1979. Zbl 0411.68039, MR 0519066 |
| Reference:
|
[3] L. Hubert: A set-theoretical approach to the problem of hierarchical clustering.Journal of Mathematical Psychology, 15 (1977), 1 pp. 70--88. Zbl 0358.62042, MR 0527187, 10.1016/0022-2496(77)90041-4 |
| Reference:
|
[4] N. Jardine, R. Sibson: Mathematical Taxonomy.Wiley, London, 1971. Zbl 0322.62065, MR 0441395 |
| Reference:
|
[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 0373375 |
| Reference:
|
[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 0806995 |
| . |
