## Abstract

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 T_{1},T_{2},...,T_{q} is obtained by deleting k = q-1 edges of T, 1 ≤ k < n. The weight W(T_{i}) (or size S(T_{i})) of component T_{i} is then the sum o weights (sizes) of the vertices of T_{i}. 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 T_{1}...,T_{q} let W_{P} = max_{1 ≤ i ≤ q} W(T_{i}). The following two problems are considered: 1. Size-constrained min-max problem: Find a q-partition of T for which W_{P} is a minimum over all partitions P satisfying S(T_{i}) ≤ M (M > 0). 2. Height-constrained min-max problem: Find a q-partition of T for which W_{P} is a minimum over all partitions P satisfying height h(T_{i}) ≤ 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) |
---|---|

Pages (from-to) | 1-28 |

Number of pages | 28 |

Journal | Discrete Applied Mathematics |

Volume | 45 |

Issue number | 1 |

DOIs | |

State | Published - Aug 2 1993 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Applied Mathematics