Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set

DOI10.4230/LIPIcs.DISC.2018.29zbMath1497.68563OpenAlexW2899261484MaRDI QIDQ5090921

Fabian Kuhn, Mohsen Ghaffari

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.DISC.2018.29

zbMATH Keywords

dominating setdistributed algorithmsderandomizationspanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (6)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Deterministic Massively Parallel Connectivity ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Distributed Spanner Approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Removing randomness in parallel computation without a processor penalty
• Sublinear fully distributed partition with applications
• Derandomizing local distributed algorithms under bandwidth restrictions
• On the locality of distributed sparse spanner construction
• Local Computation
• A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Complexity of network synchronization
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• What Can be Computed Locally?
• Distributed Graph Coloring: Fundamentals and Recent Developments
• An efficient distributed algorithm for constructing small dominating sets
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Fast randomized algorithms for distributed edge coloring
• Constant-time distributed dominating set approximation

This page was built for publication: Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set