Search Results

Documents authored by Cook, Linda


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

Authors: Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


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.

Cite 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.DISC.2021.13,
  author =	{Bonamy, Marthe and Cook, Linda and Groenland, Carla and Wesolek, Alexandra},
  title =	{{A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.13},
  URN =		{urn:nbn:de:0030-drops-148159},
  doi =		{10.4230/LIPIcs.DISC.2021.13},
  annote =	{Keywords: Outerplanar graphs, dominating set, LOCAL model, constant-factor approximation algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail