Let T = (V,E) be a rooted tree with n edges. We associate nonnegative weight w(v) and size s(v) with each vertex v in V. A q-partition of T into q connected components T1,T2,...,Tq is obtained by deleting k = q-1 edges of T, 1 ≤ k < n. The weight W(Ti) (or size S(Ti)) of component Ti is then the sum o weights (sizes) of the vertices of Ti. The height h(T) is the maximum number of edges of paths having one end at the root. If P is a partition with components T1...,Tq let WP = max1 ≤ i ≤ q W(Ti). The following two problems are considered: 1. Size-constrained min-max problem: Find a q-partition of T for which WP is a minimum over all partitions P satisfying S(Ti) ≤ M (M > 0). 2. Height-constrained min-max problem: Find a q-partition of T for which WP is a minimum over all partitions P satisfying height h(Ti) ≤ H (H is a positive integer). The first problem is shown to be NP-complete, while a polynomial algorithm is presented for the second problem.
|Original language||English (US)|
|Number of pages||28|
|Journal||Discrete Applied Mathematics|
|State||Published - Aug 2 1993|
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics