2026-08-17T09:28:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14815 2024-03-06T10:54:55Z ddc:004 open_access

A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs Bonamy, Marthe Cook, Linda Groenland, Carla Wesolek, Alexandra Outerplanar graphs dominating set LOCAL model constant-factor approximation algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marthe Bonamy and Linda Cook and Carla Groenland and Alexandra Wesolek 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.13 urn:nbn:de:0030-drops-148159 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.13 eng https://creativecommons.org/licenses/by/4.0/legalcode