Deterministic CONGEST Algorithm for MDS on Bounded Arboricity Graphs
share
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.
READ FULL TEXT