Approximation algorithms for k-source bottleneck routing cost spanning tree problems - Extended abstracts

[[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 C 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(vis an element ofV) {Sigma(sis an element ofS) d(T) (s,v)}, in which dT(8, V) is the length of the path between s 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(sis an element ofS) {Sigma(vis an element ofV) d(T) (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 + epsilon)-approximation algorithm for any epsilon > 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.[[fileno]]2030209030029[[department]]資訊工程學