Distributed Domination on Graph Classes of Bounded Expansion
| Autor: | Roman Rabinovich, Saeed Akhoondian Amiri, Sebastian Siebertz, Patrice Ossona de Mendez |
|---|---|
| Přispěvatelé: | Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Class (set theory) Approximation algorithm 020206 networking & telecommunications Graph theory 0102 computer and information sciences 02 engineering and technology Binary logarithm 01 natural sciences Planar graph Combinatorics symbols.namesake Computer Science - Distributed Parallel and Cluster Computing Cover (topology) 010201 computation theory & mathematics Dominating set Computer Science - Data Structures and Algorithms [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0202 electrical engineering electronic engineering information engineering symbols Data Structures and Algorithms (cs.DS) Distributed Parallel and Cluster Computing (cs.DC) Constant (mathematics) ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures SPAA Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, Jul 2018, Vienna, France. ⟨10.1145/3210377.3210383⟩ |
| DOI: | 10.48550/arxiv.1702.02848 |
| Popis: | We provide a new constant factor approximation algorithm for the (connected) distance-$r$ dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance-$r$ dominating set problem is currently known. Our algorithm can be implemented in the \congestbc model of distributed computing and uses $\mathcal{O}(r^2 \log n)$ communication rounds. Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an $r$-neighborhood cover of radius~$2r$ and overlap $f(r)$ on every class of bounded expansion in $\mathcal{O}(r^2 \log n)$ communication rounds for some function~$f$.% in the $\mathcal{CONGEST}_{\mathrm{BC}}$ model. Finally, we show how to use the greater power of the $\mathcal{LOCAL}$ model to turn any distance-$r$ dominating set into a constantly larger connected distance-$r$ dominating set in $3r+1$ rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al.\ gives a constant factor approximation algorithm for connected dominating sets on planar graphs in a constant number of rounds in the $\mathcal{LOCAL}$ model, where the approximation ratio is only $6$ times larger than that of Lenzen et al.'s algorithm. Comment: presented at the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|