最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．

An Approximation Algorithm for Min-Max Tree Partitioning and an Optimal Algorithm for Min-Sum Tree Partitioning

Given a weighted connected graph G = (V,E.c), we consider to partition its vortex set V into p disjoint subsets, P1,... ,Pp, in such a way that each subgraph induced by any subset obtained is connected. Our objective is either minimizing the maximum value of the weights of the minimum spanning trees of the subgraphs induced by the P.s. or, minimizing the total weight of these trees. In this paper, we first show that the problem is strongly NP-hard if its objective function is the former one and then develop a polynomial-time algorithm which is a p-approximation algorithm for the problem with the former objective function and an optimal algorithm for the problem with the latter objective function.