標題: A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
作者: Chiu, Well Y.
Chen, Chiuyuan
Tsai, Shih-Yu
應用數學系
Department of Applied Mathematics
關鍵字: Self-stabilizing algorithm;Fault tolerance;Distributed computing;Graph algorithm;Domination
公開日期: 1-Oct-2014
摘要: 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. (C) 2014 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.ipl.2014.04.011
http://hdl.handle.net/11536/24805
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2014.04.011
期刊: INFORMATION PROCESSING LETTERS
Volume: 114
Issue: 10
起始頁: 515
結束頁: 518
Appears in Collections:Articles


Files in This Item:

  1. 000338973400001.pdf