We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
SELF-STABILIZING MAXIMAL k-DEPENDENT SETS IN LINEAR TIME.
- Authors
Gairing, Martin; Goddard, Wayne; Hedetniemi, Stephen T.; Jacobs, David P.
- Abstract
In a graph or network G = (V, E), a set S C V is k-dependent if no node in S has more than k neighbors in S. We show that for each k > 0 there is a self-stabilizing algorithm that identifies a maximal k-dependent set, and stabilizes in O(kn) moves, where n is the number of nodes. An interesting by-product of our paper is the new result that in any graph there exists a set that is both maximal k-dependent and minimal (k + 1)-dominating. The set selected by our algorithm, in fact, has this property.
- Subjects
GRAPH theory; ALGORITHMS; COMPUTER algorithms; SELF-stabilization (Computer science); FAULT-tolerant computing; ELECTRONIC data processing
- Publication
Parallel Processing Letters, 2004, Vol 14, Issue 1, p75
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626404001726