Deterministic distributed construction of \(T\)-dominating sets in time \(T\)

DOI10.1016/J.DAM.2017.01.012zbMath1396.05086arXiv1705.01229OpenAlexW2588377248MaRDI QIDQ1786883

Avery Miller, Andrzej Pelc

Publication date: 25 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmundirected network\(\mathcal{LOCAL}\) model\(T\)-dominating set

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Cites Work

• Distributed approximation of capacitated dominating sets
• Combinatorial algorithms for distributed graph coloring
• Beeping a maximal independent set
• Leveraging Linial’s Locality Limit
• Locality in Distributed Graph Algorithms
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Graph Coloring: Fundamentals and Recent Developments
• An efficient distributed algorithm for constructing small dominating sets
• Maximal independent sets in radio networks
• Distributed Computing
• Constant-time distributed dominating set approximation

This page was built for publication: Deterministic distributed construction of \(T\)-dominating sets in time \(T\)