Approximation algorithms for some optimum communication spanning tree problems

Approximation algorithms for some optimum communication spanning tree problems

0.00 Avg rating0 Votes
Article ID: iaor20029
Country: Netherlands
Volume: 102
Issue: 3
Start Page Number: 245
End Page Number: 266
Publication Date: Jun 2000
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: heuristics, networks
Abstract:

Let G=(V,E,w) be an undirected graph with nonnegative edge length function w and nonnegative vertex weight function r. The optimal product-requirement communication spanning tree (PROCT) problem is to find a spanning tree T minimizing &Sgr;u,v∈Vr(u)r(v)dT(u,v), where dT(u,v) is the length of the path between u and v on T. The optimal sum-requirement communication spanning tree (SROCT) problem is to find a spanning tree T such that &Sgr;u,v∈V(r(u)+r(v))dT(u,v) is minimized. Both problems are special cases of the optimum communication spanning tree problem, and are reduced to the minimum routing cost spanning tree (MRCT) problem when all the vertex weights are equal to each other. In this paper, we present an O(n5)-time 1.577-approximation algorithm for the PROCT problem, and an O(n3) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices. We also show that a 1.577-approximation solution for the MRCT problem can be obtained in O(n3)-time, which improves the time complexity of the previous result.

Reviews

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