A Self-Stabilizing Distributed Algorithm for the Steiner Tree Problem(<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• Self-stabilization is a theoretical framework of nonmasking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a selfstabilizing 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.

• 社団法人電子情報通信学会の論文
• 2004-02-01

著者

• Kamei Sayaka

  Department Of Information Engineering Graduate School Of Engineering Hiroshima University

• KAKUGAWA Hirotsugu

  Department of Information Engineering, Hiroshima University

• Kakugawa Hirotsugu

  Department Of Information Engineering Hiroshima University

関連論文

• Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
• A Self-Stabilizing Approximation Algorithm for the Distributed Minimum k-Domination(Discrete Mathematics and Its Applications)
• A Self-Stabilizing Distributed Algorithm for the Steiner Tree Problem(Foundations of Computer Science)

スポンサーリンク