A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem
Document Type
Article
Publication Date
1-1-2019
Publication Title
Theoretical Computer Science
Volume
753
First page number:
35
Last page number:
63
Abstract
We give a silent self-stabilizing algorithm for the generalized minimal k-dominating set problem in a connected distributed network G. Given a positive integer k and two sets of processes R∗ ⊆ D∗, the problem is to find a set D which is minimal subject to the conditions that R∗ ⊆ D ⊆ D∗ and that D is k-dominating relative to D∗, meaning that every process within distance k of D∗ is also within distance k of D. The algorithm is order-invariant, requires O(log N + logk) space per process, works under the distributed unfair scheduler, and converges in O(N + k) rounds, where N is a given upper bound on the number of processes.
Keywords
Dominating Set; Self-Stabilization; Unison; Proof Labeling Scheme
Disciplines
Computer Sciences | Physical Sciences and Mathematics | Theory and Algorithms
Language
English
Repository Citation
Larmore, L.,
Datta, A.,
Université de Bordeaux, S.
(2019).
A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem.
Theoretical Computer Science, 753
35-63.
http://dx.doi.org/10.1016/j.tcs.2018.06.040