Approximation Algorithms for 2-Source Minimum Routing Cost k-Tree Problems

摘要

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_1, s_2 ￡ 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_t,E_t) spanning k vertices such that the total distance from all vertex in V_t to the two sources is minimized, I.e., we want to minimize Σ_(v∈V_T){d_T(s_1,v)+d_T(s_2,v)}, in which d_T(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_t, I.e., max_(s∈(s_1,s_2)){Σ_(v∈V_T)d_T(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_t to the two sources , I.e., max_(v∈V_T)){d_T(s_1,v)+ d_T{s_2,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.