Křivánek, Mirko A note on the computational complexity of hierarchical overlapping clustering. (English) Zbl 0581.62052 Apl. Mat. 30, 453-460 (1985). 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 investigated. It is shown that the underlying decision problems are NP- complete. MSC: 62H30 Classification and discrimination; cluster analysis (statistical aspects) 68Q25 Analysis of algorithms and problem complexity Keywords:hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; k-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete PDF BibTeX XML Cite \textit{M. Křivánek}, Apl. Mat. 30, 453--460 (1985; Zbl 0581.62052) Full Text: EuDML References: [1] E. Diday: Une représentation visuelle des classes empiétantes - les pyramides. Rap. de Recherche No 291, INRIA, Rocquencourt, 1984. · Zbl 0592.62052 [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 [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 [4] N. Jardine, R. Sibson: Mathematical Taxonomy. Wiley, London, 1971. · Zbl 0322.62065 [5] R. M. Karp: Red liability among combinatorial problems. Complexity of computer computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. [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. · Zbl 0577.62058 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.