The Geometry of Triadic Distances

Consider N entities to be classified (e.g., geographical areas), a matrix of dissimilaritiesbetween pairs of entities, a graph H with vertices associated with these entities such that the edges join the vertices corresponding to contiguous entities. The split of acluster is the smallest dissimilarity between an entity of this cluster and an entity outside ofit. The single-linkage algorithm (ignoring contiguity between entities) provides partitions into M clusters for which the smallest split of the clusters, called split of the partition, ismaximum. We study here the partitioning of the set of entities into M connected clustersfor all M between N - 1 and 2 (i.e., clusters such that the subgraphs of H induced by theircorresponding sets of entities are connected) with maximum split subject to that condition.We first provide an exact algorithm with a (N²) complexity for the particular case in which H is a tree. This algorithm suggests in turn a first heuristic algorithm for the general problem. Several variants of this heuristic are Also explored. We then present an exactalgorithm for the general case based on iterative determination of cocycles of subtrees and on the solution of auxiliary set covering problems. As solution of the latter problems istime-consuming for large instances, we provide another heuristic in which the auxiliaryset covering problems are solved approximately. Computational results obtained with theexact and heuristic algorithms are presented on test problems from the literature.