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
2107
total views13
total downloads0
views this month0
downloads this month