Deterministic Distributed Dominating Set Approximation in the CONGEST Model

DOI10.1145/3293611.3331626OpenAlexW2963158951WikidataQ130877453 ScholiaQ130877453MaRDI QIDQ5145186FDOQ5145186

Janosch Deurer, Yannic Maus, Fabian Kuhn

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.10775

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (11)

• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Deterministic Massively Parallel Connectivity
• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Distributed Dominating Set Approximations beyond Planar Graphs
• Near-optimal distributed dominating set in bounded arboricity graphs
• Distributed approximation of capacitated dominating sets
• Coloring fast without learning your neighbors' colors
• Improved hardness of approximation of diameter in the CONGEST model
• Network Decomposition and Distributed Derandomization (Invited Paper)

This page was built for publication: Deterministic Distributed Dominating Set Approximation in the CONGEST Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145186)