Deterministic CONGEST Algorithm for MDS on Bounded Arboricity Graphs

preprint2021arXivOpen access

We provide a deterministic CONGEST algorithm to constant factor approximate the minimum dominating set on graphs of bounded arboricity in $O(\log n)$ rounds. This improves over the well-known randomized algorithm of Lenzen and Wattenhofer[DISC2010] by making it a deterministic algorithm.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

Deterministic CONGEST Algorithm for MDS on Bounded Arboricity Graphs

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0