APPROXIMATION ALGORITHMS FOR MIN-MAX TREE PARTITION

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polyn omial algorithm with bounded error ratio can be given for the problem unless P = NP. We present an O(n(2)) time algorithm for the problem, w here n is the number of nodes in the graph. Assuming that the edge len gths satisfy the triangle inequality, its error ratio is at most 2p - 1. We also present an improved algorithm that obtains as an input a po sitive integer x. It runs in O(2((p+x)p)n(2)) time, and its error rati o is at most (2 - x/(x + p - 1))p. (C) 1997 Academic Press.