Simple Distributed Algorithms for Approzimating Minimum Steiner Trees
Given a network G=(V, E), edge weights w(·), and a set of terminals S (∪) V, the minimum-weight Steiner tree problem is to find a tree in G that spans S with minimum weight. Most provable heuristics treat the network G is a metric; This assumption, in a distributed setting, cannot be easily achieved without a subtle overhead. We give a simple distributed algorithm based on a minimum spanning tree heuristic that returns a solution whose cost is within a factor of two of the optimal. The algorithM runs in time O(|V| log |V|) on a synchronous network. We also show that another heuristic based on iteratively finding shortest paths gives a Θ(log|V|)approximation using a novel charging scheme based on lowcongestion routing on trees. Both algorithms work for unit-cost and general cost cases. The algorithms also have applications in finding multicast trees in wireless ad hoc networks.
Parinya Chalermsook Jittat Fakcharoenphol
Asian Institute of Technology, Pathumthanim, Thailand Kasetsart University, Bangkok, Thailand Department of Computer Engineering Kasetsart University, Bangkok, Thailand
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
380-389
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）