Abstract
In this paper, we investigate two spanning tree problems of graphs with k given sources. Let G = (V, E, w) be an undirected graph with nonnegative edge lengths and S ⊂ V a set of k specified sources. The first problem is the k-source bottleneck vertex routing cost spanning tree (k-BVRT) problem, in which we want to find a spanning tree T such that the maximum total distance from any vertex to all sources is minimized, i.e., we want to minimize max <sub>v∈v</sub> {∑ <sub>s∈S</sub> d <sub>T</sub> (s,v)}, in which d <sub>T</sub> (s, v) is the length of the path between 3 and v on T. The other problem is the k-source bottleneck source routing cost spanning tree (k-BSRT) problem, in which the objective function is the maximum total distance from any source to all vertices, i.e., max <sub>s∈S</sub> {∑ <sub>v∈V</sub> d <sub>T</sub> (s,v)}. In this paper, we present a polynomial time approximation scheme (PTAS) for the 2-BVRT problem. For the 2-BSRT problem, we first give (2 + ε)-approximation algorithm for any ε > 0, and then present a PTAS for the case that the input graphs are restricted to metric graphs. Finally we show that there is a simple 3-approximation algorithm for both the two problems with arbitrary k. © Springer-Verlag Berlin Heidelberg 2004.