کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428508 | 686790 | 2014 | 4 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon](/preview/png/428508.png)
• We propose a self-stabilizing algorithm for finding a minimal dominating set on a graph.
• This algorithm takes 4n moves and is under an unfair distributed daemon.
• This algorithm improves the previous best result, which takes 5n moves.
A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., 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 [9]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm.
Journal: Information Processing Letters - Volume 114, Issue 10, October 2014, Pages 515–518