Local algorithms in (weakly) coloured graphs

Details Local algorithms in (weakly) coloured graphs Local algorithms in (weakly) coloured graphs

2010-01-31

arxiv.org/abs/1002.0125v1

Computer Science

Distributed, Parallel, and Cluster Computing

14 pages, 3 figures

Scientific paper

A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We present local approximation algorithms for the minimum dominating set problem and the maximum matching problem in 2-coloured and weakly 2-coloured graphs. In a weakly 2-coloured graph, both problems admit a local algorithm with the approximation factor $(\Delta+1)/2$, where $\Delta$ is the maximum degree of the graph. We also give a matching lower bound proving that there is no local algorithm with a better approximation factor for either of these problems. Furthermore, we show that the stronger assumption of a 2-colouring does not help in the case of the dominating set problem, but there is a local approximation scheme for the maximum matching problem in 2-coloured graphs.

Affiliated with

Also associated with

No associations

Rating

Local algorithms in (weakly) coloured graphs 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 Local algorithms in (weakly) coloured graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local algorithms in (weakly) coloured graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-347382