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 · doi:10.1145/2611462.2611504

authors’ version publisher’s version arXiv.org

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

Links

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.