TY - GEN

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

AU - Chiu, Well Y.

AU - Chen, Chiuyuan

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893091217&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45278-9_11

DO - 10.1007/978-3-642-45278-9_11

M3 - Conference contribution

AN - SCOPUS:84893091217

SN - 9783642452772

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 126

BT - Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers

T2 - 24th International Workshop on Combinatorial Algorithms, IWOCA 2013

Y2 - 10 July 2013 through 12 July 2013

ER -