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 algorithms (68W15) Distributed systems (68M14)

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

(21)

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

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)