Miikka Hilke · Christoph Lenzen · Jukka Suomela

# Brief announcement: Local approximability of minimum dominating set on planar graphs

PODC 2014 · 33rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Paris, France, July 2014 ·

# Abstract

We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-\epsilon)$-approximation of a minimum dominating set on planar graphs, for any positive constant $\epsilon$. In prior work, the best lower bound on the approximation ratio has been $5-\epsilon$; there is also an upper bound of $52$.

# Publication

Magnús Halldórsson and Shlomi Dolev (Eds.): PODC’14, Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, July 15–18, 2014, Paris, France, pages 344–346, ACM Press, New York, 2014

ISBN 978-1-4503-2944-6