F.2:ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3)
F.2
Beschreibung:
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.