For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Self-Stabilizing Distributed Algorithm for the Steiner Tree Problem
Sayaka KAMEI Hirotsugu KAKUGAWA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/02/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
distributed algorithm, fault-tolerant, self-stabilizing algorithm, fair composition, Steiner tree problem,
Full Text: PDF(920.5KB)>>
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.