Suppression Distance Computation for Hierarchical Clusterings

By

François Queyroi, Sergey Kirgizov

Information Processing Letters, Volume 115, Issue 9, September 2015, Pages 689–693 http://www.sciencedirect.com/science/article/pii/S0020019015000678

Abstract

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.

This entry was posted in Papers