Deterministic distributed dominating set approximation in the CONGEST model

DOI10.1145/3293611.3331626MaRDI QIDQ5145186zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(24)

• Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
• Deterministic distributed ruling sets of line graphs
• Revisiting connected dominating sets: an almost optimal local information algorithm
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Minimum dominating set approximation in graphs of bounded arboricity
• Distributed Dominating Set Approximations beyond Planar Graphs
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Hardness of Distributed Optimization
• Near-optimal distributed approximation of minimum-weight connected dominating set
• Distributed Almost Exact Approximations for Minor-Closed Families
• Constant-time distributed dominating set approximation
• Constant-time distributed dominating set approximation
• Distributed distance-r covering problems on sparse high-girth graphs
• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Distributed approximation of capacitated dominating sets
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Improved hardness of approximation of diameter in the CONGEST model
• Coloring fast without learning your neighbors' colors
• Near-optimal distributed dominating set in bounded arboricity graphs
• Faster leader election via mobile agents and its applications
• The message complexity of distributed graph optimization
• Local distributed rounding: generalized to MIS, matching, set cover, and beyond
• Distributed symmetry breaking on power graphs via sparsification
• Optimal (degree+1)-coloring in congested clique

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)