Divider-based algorithms for hierarchical tree partitioning

We present algorithms for computing hierarchical decompositions of trees satisfying different optimization criteria, including balanced cluster size, bounded number of clusters, and logarithmic depth of the decomposition. Furthermore, every high-level representation of the tree obtained from such decompositions is guaranteed to be a tree. These criteria are relevant in many application settings, but appear to be difficult to achieve simultaneously. Our algorithms work by vertex deletion and hinge upon the new concept of t-divider, that generalizes the well-known concepts of centroid and separator. The use of t-dividers, combined with a reduction to a classical scheduling problem, yields an algorithm that, given a n-vertex tree T, builds in O(n log n) worst-case time a hierarchical decomposition of T satisfying all the aforementioned requirements. (C) 2003 Published by Elsevier B.V.