Deterministic distributed dominating set approximation in the CONGEST model

DOI10.1145/3293611.3331626OpenAlexW2963158951WikidataQ130877453 ScholiaQ130877453MaRDI QIDQ5145186FDOQ5145186

Authors: Janosch Deurer, Fabian Kuhn, Yannic Maus 

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

Recommendations

• Near-optimal distributed approximation of minimum-weight connected dominating set
• Constant-time distributed dominating set approximation
• Constant-time distributed dominating set approximation
• Distributed Almost Exact Approximations for Minor-Closed Families
• An efficient distributed algorithm for constructing small dominating sets

Mathematics Subject Classification ID

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

Cited In (14)

• Minimum dominating set approximation in graphs of bounded arboricity
• 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 Almost Exact Approximations for Minor-Closed Families
• Distributed approximation of capacitated dominating sets
• Coloring fast without learning your neighbors' colors
• Improved hardness of approximation of diameter in the CONGEST model
• Constant-time distributed dominating set approximation
• 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)