Titel: Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set
Sprache: Englisch
Autor/Autorin: Hauck, Bernd
Schlagwörter: self-stabilization;weakly connected minimal dominating set;complexity analysis
Erscheinungsdatum: 2008
Zusammenfassung (englisch): 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.
URI: http://tubdok.tub.tuhh.de/handle/11420/439
URN: urn:nbn:de:gbv:830-tubdok-5126
DOI: 10.15480/882.437
Institut: Telematik E-17
Telematics Institute E-17 (Telematics)
Dokumenttyp: Report (Bericht)
Enthalten in den Sammlungen:tub.dok

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
TR_submitted.pdf250,12 kBAdobe PDFMiniaturbild
Öffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.