A self-stabilizing algorithm for finding a minimal K-dominating set in general networks
Paper
Paper/Presentation Title | A self-stabilizing algorithm for finding a minimal K-dominating set in general networks |
---|---|
Presentation Type | Paper |
Authors | Wang, Guangyuan (Author), Wang, Hua (Author), Tao, Xiaohui (Author) and Zhang, Ji (Author) |
Editors | Xiang, Yang, Pathan, Mukaddim, Tao, Xiaohui and Wan g, Hua |
Journal or Proceedings Title | Lecture Notes in Computer Science (Book series) |
Data and Knowledge Engineering | |
Journal Citation | 7696, pp. 74-85 |
Number of Pages | 12 |
Year | 2012 |
Publisher | Springer |
Place of Publication | Berlin, Germany |
ISSN | 1611-3349 |
0302-9743 | |
0169-023X | |
1872-6933 | |
ISBN | 9783642346781 |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-642-34679-8_8 |
Web Address (URL) of Paper | http://link.springer.com/chapter/10.1007/978-3-642-34679-8_8# |
Conference/Event | 3rd International Conference on Data and Knowledge Engineering (ICDKE 2012) |
Event Details | 3rd International Conference on Data and Knowledge Engineering (ICDKE 2012) Event Date 21 to end of 23 Nov 2012 Event Location Fujian, China |
Abstract | Since the publication of Dijkstra's pioneering paper, a lot of self-stabilizing algorithms for computing dominating sets have been proposed in the literature. However, there is no self-stabilizing algorithm for the minimal k-dominating set (MKDS) in arbitrary graphs that works under a distributed daemon. The proposed algorithms for the minimal k-dominating set (MKDS) either work for trees (Kamei and Kakugawa [16]) or find a minimal 2-dominating set (Huang et al. [14,15]). In this paper, we propose a self-stabilizing algorithm for the minimal k-dominating set (MKDS) under a central daemon model when operating in any general network. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n2) steps where n is the number of nodes in the network. |
Keywords | self-stabilizing algorithm; minimal k-dominating set; central daemon model; general network; convergence |
ANZSRC Field of Research 2020 | 460609. Networking and communications |
469999. Other information and computing sciences not elsewhere classified | |
490399. Numerical and computational mathematics not elsewhere classified | |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Department of Mathematics and Computing |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q1y40/a-self-stabilizing-algorithm-for-finding-a-minimal-k-dominating-set-in-general-networks
1985
total views13
total downloads4
views this month0
downloads this month