Minimising k-dominating set in arbitrary network graphs
Paper
Paper/Presentation Title | Minimising k-dominating set in arbitrary network graphs |
---|---|
Presentation Type | Paper |
Authors | Wang, Guangyuan (Author), Wang, Hua (Author), Tao, Xiaohui (Author), Zhang, Ji (Author) and Zhang, Jinhua (Author) |
Editors | Motoda, Hiroshi, Wu, Zhaohui, Cao, Longbing, Zaiane, Osmar, Yao, Min and Wang, Wei |
Journal or Proceedings Title | Lecture Notes in Computer Science (Book series) |
ERA Conference ID | 43204 |
Journal Citation | 8347 (Part 2), pp. 120-132 |
Number of Pages | 13 |
Year | 2013 |
Publisher | Springer |
Place of Publication | Heidelberg, Germany |
ISSN | 1611-3349 |
0302-9743 | |
ISBN | 9783642539169 |
9783642539176 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-642-53917-6_11 |
Web Address (URL) of Paper | https://link.springer.com/chapter/10.1007/978-3-642-53917-6_11 |
Conference/Event | 9th International Conference on Advanced Data Mining and Applications (ADMA 2013) |
International Conference on Advanced Data Mining and Applications | |
Event Details | International Conference on Advanced Data Mining and Applications ADMA Rank B B B B B B B B B B B B B B B B B B B B |
Event Details | 9th International Conference on Advanced Data Mining and Applications (ADMA 2013) Event Date 14 to end of 16 Dec 2013 Event Location Hangzhou, China |
Abstract | A self-stabilizing algorithm, after transient faults hit the system and place it in some arbitrary global state, recovers in finite time without external (e.g., human) intervention. A k-dominating set in a distributed system is a set of processors such that each processor outside the set has at least k neighbors in the set. In the past, a few self-stabilizing algorithms for minimal k-dominating set (MKDS) have been obtained. However, the presented self-stabilizing algorithms for MKDS work for either trees or a minimal 2-dominating set. Recently a self-stabilizing algorithm for MKDS in arbitrary graphs under a central daemon has been investigated. But so far, there is no algorithm for the MKDS problem in arbitrary graphs that works under a distributed daemon. In this paper, we propose a self-stabilizing algorithm for finding a MKDS under a distributed daemon model when operating in any general network graph. We further verify the correctness of the proposed algorithm (Algorithm MKDS) and prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n 2) steps where n is the number of nodes in the network. |
Keywords | self-stabilizing algorithm; minimal k-dominating set; distributed daemon model; arbitrary network; convergence |
ANZSRC Field of Research 2020 | 400604. Network engineering |
460207. Modelling and simulation | |
461399. Theory of computation not elsewhere classified | |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Department of Mathematics and Computing |
Beijing Normal University, China | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q2663/minimising-k-dominating-set-in-arbitrary-network-graphs
1678
total views21
total downloads1
views this month0
downloads this month