Publications
Home PageLocal algorithms in (weakly) coloured graphs
| Authors: | Matti Åstrand Valentin Polishchuk Joel Rybicki Jukka Suomela Jara Uitto |
| Title: | Local algorithms in (weakly) coloured graphs |
| Date: | February 2009 |
| Links: | manuscript |
| Abstract: | A
local algorithm is a distributed algorithm that completes after a
constant number of synchronous communication rounds. We study local
approximation algorithms for the minimum dominating set problem and the
maximum matching problem in 2-coloured and weakly 2-coloured graphs. We
show that in a weakly 2-coloured graph, both problems admit a local
algorithm with the approximation factor (Δ + 1)/2, where Δ 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. |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

