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

Peer reviewed: 
Yes, item is peer reviewed.
Scholarly level: 
Graduate student (PhD)
Final version published as: 

Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A tight local algorithm for the minimum dominating set problem in outerplanar graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. DOI: 10.4230/LIPIcs.DISC.2021.13.

Date created: 
2021-10-04
Identifier: 
DOI: 10.4230/LIPIcs.DISC.2021.13
Keywords: 
Outerplanar graphs
Dominating set
LOCAL model
Constant-factor approximation algorithm
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.

Language: 
English
Document type: 
Article
File(s): 
Statistics: