Approximation algorithm for the balanced 2-connected k-partition problem

摘要

For two positive integers m, k and a connected graph G = (V, E) with a nonnegative vertex weight function w, the balanced m-connected k-partition problem, denoted as BCm P-k, is to find a partition of V into k disjoint nonempty vertex subsets (V-1, V-2,..., V-k) such that each G[V-i] (the subgraph of G induced by V-i) is m-connected, and min(1 <= i <= k){w(V-i)} is maximized. The optimal value of BCm P-k on graph G is denoted as beta(m)*(G, k), that is, beta(m)*(G, k) = max min(1 <= i <= k){w(V-i)}, where the maximum is taken over all m-connected k-partition of G. In this paper, we study the BC2 P-k problem on interval graphs, and obtain the following results.