Tree partitioning under constraints – clustering for vehicle routing problems

We present a dynamic programming algorithm for the following problem: Given a tree T = (V,E), a set of q non-negative integer weights wi: V ÷ N on the nodes, and a threshold Ri, i = 1, …, q, partition the vertices of the tree into connected components T0, …, Tk, such that for all i5{1, …, q}, j5{0, …, k} >χ5T, wi (χ)″ Ri and k is minimal. We show that this problem is hard, if q is unbounded or if T has unbounded maximum degree. In all other cases the running time of the dynamic program has a polynomial worst-case bound.