Distributed domination on sparse graph classes.

We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with bounded expansion. This generalizes a result of Czygrinow et al. for graphs with excluded topological minors to very general classes of uniformly sparse graphs. We demonstrate how our general algorithm can be modified and fine-tuned to compute an (11 + ɛ)-approximation (for any ɛ > 0) of a minimum dominating set on planar graphs. This improves on the previously best known approximation factor of 52 on planar graphs, which was achieved by an elegant and simple algorithm of Lenzen et al. [ABSTRACT FROM AUTHOR]

Copyright of European Journal of Combinatorics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)