A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees

Abstract

Let T = (V,E) be a rooted tree with n edges. We associate a non‐negative weight w(v) with each vertex v in V. A q‐partition of T into q connected components T₁,...,T_q is obtained by deleting k = q‐1 edges of T, 1<=q<=n. Let w(T_i) denote the sum of the weights of the vertices in T_i. The height of 7] is denoted by h(T_i).

The following problem is considered: Given W, H>0, find a q‐partition satisfying w(T_i) <=W, height (T_i) <=,H (1<=i<=q) for which q is a minimum.

A bottom‐up polynomial time algorithm is given for this problem which has complexity 0(Hn), or independently of H, 0(height(T)n).

Keywords:

• Tree partitioning
• bottom‐up algorithm
• constrained partitioning

C.R. Categories::

• F2.2
• G2.1
• G2.2

This research was supported in part by the Council for Scientific and Industrial Research, Pretoria, South Africa

This research was supported in part by the Council for Scientific and Industrial Research, Pretoria, South Africa

Notes

This research was supported in part by the Council for Scientific and Industrial Research, Pretoria, South Africa