A tight local algorithm for the minimum dominating set problem in outerplanar graphs

08/05/2021
by   Marthe Bonamy, et al.
0

We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a (5-ε)-approximation, for any ε>0. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset