Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set
Bernd Hauck · tub.dok (Hamburg University of Technology) · 2008
Recently, Srimani and Xu presented a self-stabilizing algorithm that computes a weakly connected minimal dominating set. They prove an upper bound of O(2^n) until stabilization but they do not provide a lower bound. This paper verifies by giving an example that their algorithm indeed requires O(2^n) moves on a certain graph.