Name
Abstract | ||
|---|---|---|
We consider a connected undirected graph G(n,m) with n nodes and m edges. A k-dominating set D in G is a set of nodes having the property that every node in G is at most k edges away from at least one node in D. Finding a k-dominating set of minimum size is NP-hard. We give a new synchronous distributed algorithm to find a k-dominating set in G of size no greater than [n/(k+1)]. Our algorithm requires O(k log* n) time and O(m log k+n log k log* n) messages to run. It has the same time complexity as the best currently known algorithm, but improves on that algorithm's message complexity and is, in addition, conceptually simpler. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0166-218X(03)00368-8 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
dominating set,distributed algorithm | Journal | 141 |
Issue | ISSN | Citations |
1-3 | Discrete Applied Mathematics | 15 |
PageRank | References | Authors |
0.77 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucia Draque Penso | 1 | 196 | 20.46 |
| Valmir C. Barbosa | 2 | 350 | 56.76 |
| PensoLucia Draque | 3 | 15 | 0.77 |