Simple distributed algorithms for approximating minimum steiner trees

Parinya Chalermsook*, Jittat Fakcharoenphol

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

16 Citations (Scopus)

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 languageEnglish
Pages (from-to)380-389
Number of pages10
JournalLecture Notes in Computer Science
Volume3595
Publication statusPublished - 2005
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Simple distributed algorithms for approximating minimum steiner trees'. Together they form a unique fingerprint.

Cite this