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.

Divider-based algorithms for hierarchical tree partitioning / Finocchi, Irene; Petreschi, Rossella. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 136:2-3(2004), pp. 227-247. [10.1016/s0166-218x(03)00443-8]

Divider-based algorithms for hierarchical tree partitioning

Irene Finocchi;
2004

Abstract

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.
centroids; graph partitioning problems; hierarchical decompositions; trees
Divider-based algorithms for hierarchical tree partitioning / Finocchi, Irene; Petreschi, Rossella. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 136:2-3(2004), pp. 227-247. [10.1016/s0166-218x(03)00443-8]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/192645
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact