Linear-time self-stabilizing algorithms for minimal domination in graphs

Well Y. Chiu, Chiuyuan Chen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


A distributed system is self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [6]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes. In 2008, Goddard et al. [2] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm. We also prove that if an MDS-silent algorithm is preferred, then distance-1 knowledge is insufficient, where a self-stabilizing MDS algorithm is MDS-silent if it will not make any move when the starting configuration of the system is already an MDS.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Number of pages12
StatePublished - 1 Dec 2013
Event24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France
Duration: 10 Jul 201312 Jul 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Workshop on Combinatorial Algorithms, IWOCA 2013


Dive into the research topics of 'Linear-time self-stabilizing algorithms for minimal domination in graphs'. Together they form a unique fingerprint.

Cite this