Paper Info
Title
Local algorithms in (weakly) coloured graphs
Abstract
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.
Year
Venue
Keywords
2010
Clinical Orthopaedics and Related Research
cluster computing,maximum degree,synchronous communication,maximum matching,distributed algorithm,lower bound,dominating set
Field
DocType
Volume
Approximation algorithm,Combinatorics,Mathematical optimization,Dominating set,Computer science,Bipartite graph,Hopcroft–Karp algorithm,Matching (graph theory),Local algorithm,Vertex cover,Distributed computing,Maximal independent set
Journal
abs/1002.0
Citations 
PageRank 
References 
6
0.69
10
Authors
5
Name
Order
Citations
PageRank
Matti Åstrand1462.23
Valentin Polishchuk225234.51
Joel Rybicki3789.69
Jukka Suomela460046.99
Jara Uitto510717.08