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

Conference paper (2021)

Authors

Linda Cook Institute for Basic Science (IBS)
C.E. Groenland Universiteit Utrecht
Alexandra Wesolek Simon Fraser University
Affiliation
External organisation
Constant-factor approximation algorithm Dominating set LOCAL model Outerplanar graphs
More Info
expand_more

Published Date

2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.