Approximation algorithms for some k-source shortest paths spanning tree problems

Approximation algorithms for some k-source shortest paths spanning tree problems

0.00 Avg rating0 Votes
Article ID: iaor2007379
Country: United States
Volume: 47
Issue: 3
Start Page Number: 147
End Page Number: 156
Publication Date: May 2006
Journal: Networks
Authors: , ,
Keywords: combinatorial optimization
Abstract:

In this article, 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 maximum vertex shortest paths spanning tree (k-MVST) 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, that is, we want to minimize maxvεV{&Sgr;sεSdT(s,v)}, in which dT(s,v) is the length of the path between s and v on T. The other problem is the k-source maximum source shortest paths spanning tree (k-MSST) problem, in which the objective function is the maximum total distance from any source to all vertices, that is, max sεS{&Sgr;vεVdT(s,v)}. In this article, we present a polynomial time approximation scheme (PTAS) for the 2-MVST problem. For the 2-MSST 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 are simple 3-approximation algorithms for both problems with arbitrary k.

Reviews

Required fields are marked *. Your email address will not be published.