Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set
Pradip K. Srimani, Zhenyu Xu · 2007
In this paper, we present a self-stabilizing algorithm that computes the breadth first spanning tree in arbitrary graph, with 0(n3) time complexity using the unfair central daemon. We then propose a self-stabilizing algorithm to compute the weakly connected minimal dominating set in a graph using the same model and provide its correctness and complexity analysis; as far as we know, this is the first self-stabilizing algorithm to compute such sets.