A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs

Date created
2021-10-04
Authors/Contributors
Abstract
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.
Document
Scholarly level
Peer reviewed?
Yes
Language
Member of collection