Approximating the Minmax Rooted-Subtree Cover Problem(Graphs and Networks)

概要

論文の詳細を見る
Let G=(V, E) be a connected graph such that each edge e∈E and each vertex v∈V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X={X_1, X_2, …, X_p} of V and a set of p subtrees T_1, T_2, …, T_p such that each T_i contains X_i∪{r} so as to minimize the maximum cost of the subtrees, where the cost of T_i is defined to be the sum of the weights of edges in T_i and the weights of vertices in X_i. Similarly, the minmax rootedcycle cover problem (MRCC) asks to find a partition X={X_1, X_2, …, X_p} of V and a set of p cycles C_1, C_2, …, C_p such that C_i contains X_i∪{r} so as to minimize the maximum cost of the cycles, where the cost of C_i is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G, w).
社団法人電子情報通信学会の論文
2005-05-01