Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected  Minimal Dominating Set

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.

Subjects

self-stabilization