## Abstract

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 low-congestion 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.

Original language | English |
---|---|

Pages (from-to) | 380-389 |

Number of pages | 10 |

Journal | Lecture Notes in Computer Science |

Volume | 3595 |

Publication status | Published - 2005 |

MoE publication type | A1 Journal article-refereed |