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

UNLV article access

Find in your library

Share

COinS