Paper Info
Title
A distributed algorithm for k-dominating sets
Abstract
Abstract This paper presents a fast distributed algorithm to find a small fe-dominating set in a graph G , with n nodes and m edges, n > k + 1. A k -dominating set D of G is a set of nodes such that for every node υ of G , there exists a node of D whose distance to υ is at most k. D is said to be a small k -dominating set if it has at most [ n/k +1] nodes, which is the best lower bound for the size of D in general. The algorithm is synchronous, its time complexity is O ( k log ∗ n ) and its message complexity is O ( n log k log ∗ n ). Small k -dominating sets have applications in a number of areas, including the design of distributed data structures, the selection of servers in a network, and routing with sparse tables. Note, finally, that the decision problem related to finding the smallest k -dominating set of G is NP-Complete.
Year
DOI
Venue
2001
10.1016/S1571-0653(04)00242-2
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Distributed algorithms,k-dominating sets
Discrete mathematics,Graph,Combinatorics,Decision problem,Dominating set,Existential quantification,Upper and lower bounds,Server,Distributed algorithm,Time complexity,Mathematics
Journal
Volume
ISSN
Citations 
7
1571-0653
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Lucia Draque Penso119620.46
Valmir C. Barbosa235056.76