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

Well Y. Chiu; Chiuyuan Chen

doi:10.1007/978-3-642-45278-9_11

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

Well Y. Chiu, Chiuyuan Chen^*

^*Corresponding author for this work

Department of Applied Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

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 language	English
Title of host publication	Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Pages	115-126
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-45278-9_11
State	Published - 1 Dec 2013
Event	24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France Duration: 10 Jul 2013 → 12 Jul 2013

Publication series

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

Conference

Conference	24th International Workshop on Combinatorial Algorithms, IWOCA 2013
Country/Territory	France
City	Rouen
Period	10/07/13 → 12/07/13

Access to Document

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

Cite this

Chiu, W. Y., & Chen, C. (2013). Linear-time self-stabilizing algorithms for minimal domination in graphs. In Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers (pp. 115-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8288 LNCS). https://doi.org/10.1007/978-3-642-45278-9_11

@inproceedings{ec81397704a2406aad27a4f16391ba1b,

title = "Linear-time self-stabilizing algorithms for minimal domination in graphs",

abstract = "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.",

author = "Chiu, {Well Y.} and Chiuyuan Chen",

year = "2013",

month = dec,

day = "1",

doi = "10.1007/978-3-642-45278-9_11",

language = "English",

isbn = "9783642452772",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "115--126",

booktitle = "Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers",

note = "24th International Workshop on Combinatorial Algorithms, IWOCA 2013 ; Conference date: 10-07-2013 Through 12-07-2013",

}

Chiu, WY & Chen, C 2013, Linear-time self-stabilizing algorithms for minimal domination in graphs. in Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8288 LNCS, pp. 115-126, 24th International Workshop on Combinatorial Algorithms, IWOCA 2013, Rouen, France, 10/07/13. https://doi.org/10.1007/978-3-642-45278-9_11

Linear-time self-stabilizing algorithms for minimal domination in graphs. / Chiu, Well Y.; Chen, Chiuyuan.
Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers. 2013. p. 115-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8288 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Chiu WY, Chen C. Linear-time self-stabilizing algorithms for minimal domination in graphs. In Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers. 2013. p. 115-126. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-45278-9_11

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this