A Self-Stabilizing Distributed Algorithm for the Steiner Tree Problem

Sayaka KAMEI  Hirotsugu KAKUGAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.2   pp.299-307
Publication Date: 2004/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
distributed algorithm,  fault-tolerant,  self-stabilizing algorithm,  fair composition,  Steiner tree problem,  

Full Text: PDF>>
Buy this Article



Summary: 
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1-1/l), where l is the number of leaves of optimal solution.