A distributed algorithm to find k-dominating sets

Details A distributed algorithm to find k-dominating sets A distributed algorithm to find k-dominating sets

2003-09-23

arxiv.org/abs/cs/0309040v1

Discrete Applied Mathematics 141 (2004), 243-253

Computer Science

Distributed, Parallel, and Cluster Computing

To appear in Discrete Applied Mathematics

Scientific paper

10.1016/S0166-218X(03)00368-8

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.

Affiliated with

Also associated with

No associations

Rating

A distributed algorithm to find k-dominating sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A distributed algorithm to find k-dominating sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A distributed algorithm to find k-dominating sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182673