An efficient distributed algorithm for constructing small dominating sets

DOI10.1007/S00446-002-0078-0MaRDI QIDQ5138380zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

ad hoc networkapproximation algorithmdistributed computingdominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Constant-time distributed dominating set approximation
• Constant-time distributed dominating set approximation
• A distributed algorithm to find \(k\)-dominating sets
• A distributed algorithm for k-dominating sets
• Fast Distributed Construction of Smallk-Dominating Sets and Applications

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A derandomization using min-wise independent permutations
• A Greedy Heuristic for the Set-Covering Problem
• A parallel approximation algorithm for positive linear programming
• Approximation algorithms for combinatorial problems
• Complexity of network synchronization
• Deterministic coin tossing with applications to optimal parallel list ranking
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• How to Allocate Network Centers
• scientific article; zbMATH DE number 4209907 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• Locality in Distributed Graph Algorithms
• On the ratio of optimal integral and fractional covers
• Parallel Symmetry-Breaking in Sparse Graphs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Probabilistic recurrence relations
• Reducibility among combinatorial problems
• The local nature of \(\Delta\)-coloring and its algorithmic applications

Cited in

(38)

• Deterministic distributed construction of T-dominating sets in time T
• A distributed algorithm to find \(k\)-dominating sets
• Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
• On parallelizing a greedy heuristic for finding small dominant sets
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• A distributed algorithm for k-dominating sets
• Near-optimal dominating sets via random sampling
• Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
• A new distributed algorithm for computing a dominating set on grids
• Leveraging Linial’s Locality Limit
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• scientific article; zbMATH DE number 708868 (Why is no real title available?)
• scientific article; zbMATH DE number 2079403 (Why is no real title available?)
• scientific article; zbMATH DE number 1555925 (Why is no real title available?)
• On the microscopic view of time and messages
• Distributed spanner approximation
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Probabilistic algorithm for minimum \(k\)-fold dominating set problem
• Dominating sets and connected dominating sets in dynamic graphs
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Deterministic distributed dominating set approximation in the CONGEST model
• Near-optimal distributed approximation of minimum-weight connected dominating set
• Rapid randomized pruning for fast greedy distributed algorithms
• Enabling minimal dominating set in highly dynamic distributed systems
• Cluster-based energy-efficient secure routing in wireless sensor networks
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Algorithms – ESA 2004
• Constant-time distributed dominating set approximation
• Constant-time distributed dominating set approximation
• Beep-and-sleep: message and energy efficient set cover
• Beep-and-sleep: message and energy efficient set cover
• Near-optimal dominating sets in dense random graphs in polynomial expected time
• Near-optimal distributed dominating set in bounded arboricity graphs
• The message complexity of distributed graph optimization
• Approximation algorithms for the total dominating set problem
• Distributed algorithms for weighted problems in sparse graphs
• Distributed algorithms for random graphs

This page was built for publication: An efficient distributed algorithm for constructing small dominating sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138380)