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 w(i): V --> N on the nodes, and a threshold R-i, i = 1,...,q. Partition the vertices of the tree into connected components T-0,...,T-k, such that for all i is an elem ent of {1,...,q}, j is an element of {0,...,k} (v is an element of Tj)Sigma w(i)(v) less than or equal to R-i and k is minimal. We show that this prob lem is hard, if q is unbounded or if T has unbounded maximum degree. Ln all other cases the running time of the dynamic program has a polynomial worst -case bound. (C) 2000 Elsevier Science B.V. All rights reserved.