Аннотация
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 -
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)