Back to Search
Start Over
Self-Stabilizing Algorithms for {k}-Domination.
- Source :
- Self-Stabilizing Systems (9783540404538); 2003, p49-60, 12p
- Publication Year :
- 2003
-
Abstract
- In the self-stabilizing algorithmic paradigm for distributed computing each node has only a local view of the system, yet in a finite amount of time the system converges to a global state, satisfying some desired property. A function f : V (G) → {0, 1, 2. . . , k} is a {k}-dominating function if ΣjεN[i]f(j) ≥ k for all i ε V (G). In this paper we present self-stabilizing algorithms for finding a minimal {k}-dominating function in an arbitrary graph. Our first algorithm covers the general case, where k is arbitrary. This algorithm requires an exponential number of moves, however we believe that its scheme is interesting on its own, because it can insure that when a node moves, its neighbors hold correct values in their variables. For the case that k = 2 we propose a linear time self-stabilizing algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540404538
- Database :
- Supplemental Index
- Journal :
- Self-Stabilizing Systems (9783540404538)
- Publication Type :
- Book
- Accession number :
- 33100532
- Full Text :
- https://doi.org/10.1007/3-540-45032-7_4