An efficient distributed algorithm for constructing small dominating sets
From MaRDI portal
Publication:5138380
DOI10.1007/s00446-002-0078-0zbMath1448.68472OpenAlexW2694808592MaRDI QIDQ5138380
Lu Jun Jia, Rajmohan Rajaraman, Torsten Suel
Publication date: 3 December 2020
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-002-0078-0
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (15)
Distributed algorithms for weighted problems in sparse graphs ⋮ Distributed algorithms for random graphs ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Leveraging Linial’s Locality Limit ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Unnamed Item ⋮ On the Microscopic View of Time and Messages ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Cluster-Based Energy-Efficient Secure Routing in Wireless Sensor Networks ⋮ Distributed Spanner Approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A derandomization using min-wise independent permutations
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- A Best Possible Heuristic for the k-Center Problem
- Deterministic coin tossing with applications to optimal parallel list ranking
- Complexity of network synchronization
- Parallel Symmetry-Breaking in Sparse Graphs
- A Greedy Heuristic for the Set-Covering Problem
- Locality in Distributed Graph Algorithms
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- How to Allocate Network Centers
- Probabilistic recurrence relations
- Reducibility among Combinatorial Problems
- A parallel approximation algorithm for positive linear programming
This page was built for publication: An efficient distributed algorithm for constructing small dominating sets
