@inproceedings{1eda7af7160c4baeb5b58eaf7ca2c9ad,
title = "A tight local algorithm for the minimum dominating set problem in outerplanar graphs",
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.",
keywords = "Constant-factor approximation algorithm, Dominating set, LOCAL model, Outerplanar graphs",
author = "Marthe Bonamy and Linda Cook and Carla Groenland and Alexandra Wesolek",
year = "2021",
doi = "10.4230/LIPIcs.DISC.2021.13",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Seth Gilbert",
booktitle = "35th International Symposium on Distributed Computing, DISC 2021",
address = "Germany",
note = "35th International Symposium on Distributed Computing, DISC 2021 ; Conference date: 04-10-2021 Through 08-10-2021",
}