Titel: Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set
Sprache: English
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
DOI: 10.15480/882.437
Institut: Telematik E-17 
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
Zur Langanzeige

Seitenansichten

478
Letzte Woche
1
Letzten Monat
4
checked on 16.02.2019

Download(s)

306
checked on 16.02.2019

Google ScholarTM

Prüfe

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.