hierarchy of clusters, such that for any two different clusters $A$ and $B$ from possibly different levels of the hierarchy we either have $A \cap B = \emptyset$, $A\subset B$, or $B \subset A$. Such a hierarchy is useful in many applications, for example, when one is interested in hereditary properties of the clusters (as in some bioinformatics applications) or if the exact number of clusters is a priori unknown.

In order to define the agglomerative strategy properly, we have to specify a distance measure between clusters. Given a distance function between data objects, the following distance measures between clusters are frequently used. In the *single linkage strategy*, the distance between two clusters is defined as the distance between their closest pair of data objects. Using this strategy is equivalent to computing a minimum spanning tree of the graph induced by the distance function using Kruskal’s algorithm. In case of the *complete linkage strategy*, the distance between two clusters is defined as the distance between their farthest pair of data objects. In the *average linkage strategy* the distance is defined as the average distance between data objects from the two clusters.

Related Work
------------

In this paper, we study the 