%0 Journal Article %1 km86 %A Křivánek, Mirko %A Morávek, Jaroslav %D 1986 %J Acta Informatica %K clustering partition tree %N 3 %P 311--323 %T NP-hard problems in hierarchical-tree clustering %U http://dx.doi.org/10.1007/BF00289116 %V 23 %X We consider a class of optimization problems of 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 relatively laborious graph-theoretical constructions and starts in the NP-complete problem of 3-dimensional matching. Using our main result we establish the NP-completeness of a problem of the best approximation of a symmetric relation on a finite set by an equivalence relation, thus answering in the negative a question proposed implicitly by C.T. Zahn. ER -

@article{km86, abstract = {We consider a class of optimization problems of 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 relatively laborious graph-theoretical constructions and starts in the NP-complete problem of 3-dimensional matching. Using our main result we establish the NP-completeness of a problem of the best approximation of a symmetric relation on a finite set by an equivalence relation, thus answering in the negative a question proposed implicitly by C.T. Zahn. ER -}, added-at = {2009-07-29T23:17:39.000+0200}, author = {Křivánek, Mirko and Morávek, Jaroslav}, biburl = {https://www.bibsonomy.org/bibtex/20ee920ec4ea059ea7c8f191652bef2b0/pitman}, description = {SpringerLink - Journal Article}, interhash = {a9dd0836436f909267191c2e4b52585c}, intrahash = {0ee920ec4ea059ea7c8f191652bef2b0}, journal = {Acta Informatica}, keywords = {clustering partition tree}, number = 3, pages = {311--323}, timestamp = {2009-07-29T23:17:39.000+0200}, title = {NP-hard problems in hierarchical-tree clustering}, url = {http://dx.doi.org/10.1007/BF00289116}, volume = 23, year = 1986 }