Suppression Distance Computation for Hierarchical Clusterings

François Queyroi, Sergey Kirgizov

Information Processing Letters, Volume 115, Issue 9, September 2015, Pages 689–693

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.