21st IEEE Symposium on Reliable Distributed Systems (SRDS'02)
A Self-Stabilizing Algorithm for the Steiner Tree Problem
Osaka University, Suita, Japan
October 13-October 16
ISBN: 0-7695-1659-9
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 solution to the problem. Our solution is based on Pruned-MST technique; the Pruned-MST method is a heuristic technique to find a minimal cost Steiner tree by pruning unnecessary nodes and edges in minimum cost spanning tree, provided that a minimum spanning tree is available. Finally we propose an algorithm to reduce the cost of the solution.