Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.437
Fulltext available Open Access
Title: Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set
Language: English
Authors: Hauck, Bernd 
Keywords: self-stabilization;weakly connected minimal dominating set;complexity analysis
Issue Date: 2008
Abstract (english): 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
Institute: Telematik E-17 
Type: Report (Bericht)
License: http://doku.b.tu-harburg.de/doku/lic_mit_pod.php
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
TR_submitted.pdf250,12 kBAdobe PDFThumbnail
View/Open
Show full item record

Page view(s)

540
Last Week
1
Last month
10
checked on Sep 20, 2020

Download(s)

344
checked on Sep 20, 2020

Google ScholarTM

Check

Note about this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.