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

Well Y. Chiu, Chiuyuan Chen*

*此作品的通信作者

研究成果: Conference contribution同行評審

3 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
頁面115-126
頁數12
DOIs
出版狀態Published - 1 12月 2013
事件24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France
持續時間: 10 7月 201312 7月 2013

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
8288 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference24th International Workshop on Combinatorial Algorithms, IWOCA 2013
國家/地區France
城市Rouen
期間10/07/1312/07/13

指紋

深入研究「Linear-time self-stabilizing algorithms for minimal domination in graphs」主題。共同形成了獨特的指紋。

引用此