Let T be a tree such that edges are weighted by nonnegative reals, and p be a positive integer. The minraax subtree cover problem asks to find a set of p subtrees such that the union of the subtrees covers all vertices in T, where the objective is to minimize the maximum weight of the subtrees. Given a root r in T, the minmax rooted-subtree cover problem, asks to find a set of p subtrees such that each subtree contains the root r and the union of the subtrees covers all vertices in T, where the objective is to minimize the maximum weight of the subtrees. In this paper, we propose an O(p~2n) time (2 -2/p+1)-approximation algorithm to the first problem, and an O(nloglog1+e 3) time (2 + ε)-approximation algorithm to the second problem, where ε > 0 is a prescribed constant.
展开▼
机译：假设是一棵树，使得边缘被非负实实物加权，并且P是正整数。 Minraax子树封面问题要求找到一组P子树，使得子树的联合涵盖T的所有顶点，其中目标是最小化子树的最大重量。给定Root R中的，MinMax rooted-subtree覆盖问题，要求找到一组P子树，使得每个子树包含根r和子树的联合覆盖t的所有顶点，其中目标是最小化远子的最大重量。在本文中，我们向第一问题提出了O（P〜2N）时间（2 -2n）时间（2 -2 / p + 1）批量算法，以及O（nloglog1 + e 3）时间（2 +ε） - 达到估计算法第二问题，其中ε> 0是规定的常数。
展开▼
