Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Local algorithms in (weakly) coloured graphs   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.

29
The categories of this paper are: funct-an
31
The categories of this paper are: ao-sci
14
The categories of this paper are: math-ph
16
The categories of this paper are: stat
36
The categories of this paper are: cmp-lg
37
The categories of this paper are: supr-con
18
The categories of this paper are: econ
10
The categories of this paper are: q-bio
3
The categories of this paper are: physics
4
The categories of this paper are: cond-mat
2
The categories of this paper are: math
11
The categories of this paper are: hep-lat
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
21
The categories of this paper are: adap-org
28
The categories of this paper are: alg-geom