A distributed algorithm to find k-dominating sets
| dc.creator | Penso, L. D. | |
| dc.creator | Barbosa, V. C. | |
| dc.date | 2003-09-23 | |
| dc.date.accessioned | 2026-07-07T07:46:32Z | |
| dc.date.available | 2026-07-07T07:46:32Z | |
| dc.description | 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 $\lfloor n/(k+1)\rfloor$. 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. | |
| dc.description | To appear in Discrete Applied Mathematics | |
| dc.identifier | https://arxiv.org/abs/cs/0309040 | |
| dc.identifier | http://arxiv.org/abs/cs/0309040 | |
| dc.identifier | Discrete Applied Mathematics 141 (2004), 243-253 | |
| dc.identifier | doi:10.1016/S0166-218X(03)00368-8 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123861 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | F.1.2; F.2.2 | |
| dc.title | A distributed algorithm to find k-dominating sets | |
| dc.type | text |