Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427108 | Information Processing Letters | 2015 | 5 Pages |
Abstract
•We generalize the suppression distance defined for partitions to hierarchical clusterings.•We reduce its computation to the minimum vertex cover problem.•We prove this problem can be solved in polynomial time and provide a recursive algorithm.
We discuss the computation of a distance between two hierarchical clusterings of the same set. It is defined as the minimum number of elements that have to be removed so the remaining clusterings are equal. The problem of distance computing was extensively studied for partitions. We prove it can be solved in polynomial time in the case of hierarchies as it gives birth to a class of perfect graphs. We also propose an algorithm based on recursively computing maximum assignments.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
François Queyroi, Sergey Kirgizov,