On NP-Hardness in Hierarchical Clustering
Mirko Kr̆ivánek, Jaroslav Morávek · 1984
We consider a class of optimization problems of the hierarchical-tree clustering, and prove that these problems are NP-hard. The sequence of polynomial reductions and/or transformations used in our proof is based on graph-theoretical techniques and constructions, and starts in the NP-complete problem of 5-dimensional matching.