A note on the computational complexity of hierarchical overlapping clustering
Mirko Kr̆ivánek · Applications of Mathematics · 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 investigared. It is shown that the underlying decision problems are NP-complete.