On the Complexity of Ordinal Clustering |
| |
Authors: | Rahul Shah Martin Farach-Colton |
| |
Institution: | (1) Purdue University, West Lafayette IN, USA;(2) Rutgers University, Piscataway NJ, USA |
| |
Abstract: | Given a set of pairwise distances on a set of n points, constructing an edgeweighted tree whose leaves are these n points
such that the tree distances would mimic the original distances under some criteria is a fundamental problem. One such criterion
is to preserve the ordinal relation between the pairwise distances. The ordinal relation can be of the form of total order
on the distances or it can be some partial order specified on the pairwise distances. We show that the problem of finding
a weighted tree, if it exists, which would preserve the total order on pairwise distances is NP-hard. We also show the NP-hardness
of the problem of finding a weighted tree which would preserve a particular kind of partial order called a triangle order,
one of the most fundamental partial orders considered in computational biology. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|