Abstract
In this paper, we investigate some k-tree problems of graphs with given two sources. Let G = (V, E, w) be an undirected graph with nonnegative edge lengths and two sources S <sub>1</sub> , S <sub>2</sub> ∈ V. The first problem is the 2-source minimum routing cost k-tree (2-kMRCT) problem, in which we want to find a tree T = (V <sub>T</sub> , E <sub>T</sub> ) spanning k vertices such that the total distance from all vertex in V <sub>T</sub> to the two sources is minimized, i.e., we want to minimize Σ <sub>v∈VT</sub> {d <sub>T</sub> (s <sub>1</sub> , v) + d <sub>T</sub> (s <sub>2</sub> , v)}in which d <sub>T</sub> (s, v) is the length of the path between s and v on T. The second problem is the 2-source bottleneck source routing cost k-tree (2-kBSRT) problem, in which the objective function is the maximum total distance from any source to all vertices in V <sub>T</sub> , i.e., maxs <sub>∈(s1,s2)</sub> {Σ <sub>v∈VT</sub> d <sub>T</sub> (s,v)}. The third problem is the 2-source bottleneck vertex routing cost k-tree (2-kBVRT) problem, in which the objective function is the maximum total distance from any vertex in V <sub>T</sub> to the two sources , i.e., max <sub>v∈VT</sub> {d <sub>T</sub> (s <sub>1</sub> , v) + d <sub>T</sub> (s <sub>2</sub> , v)}. In this paper, we present polynomial time approximation schemes (PTASs) for the 2-kMRCT and 2-kBVRT problems. For the 2-kBSRT problem, we give a (2 + ε)-approximation algorithm for any ε > 0. © Springer-Verlag Berlin Heidelberg 2007.