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 -