Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set
Citation Link: https://doi.org/10.15480/882.437
Publikationstyp
Technical Report
Date Issued
2008
Sprache
English
Author(s)
Institut
TORE-DOI
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
weakly connected minimal dominating set
complexity analysis