Constant-time distributed dominating set approximation
From MaRDI portal
Recommendations
- Constant-time distributed dominating set approximation
- An efficient distributed algorithm for constructing small dominating sets
- Deterministic distributed dominating set approximation in the CONGEST model
- Near-optimal distributed approximation of minimum-weight connected dominating set
- A distributed algorithm to find \(k\)-dominating sets
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256762 (Why is no real title available?)
- scientific article; zbMATH DE number 2079403 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A parallel approximation algorithm for positive linear programming
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- Approximation algorithms for connected dominating sets
- Discrete mobile centers
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- On the ratio of optimal integral and fractional covers
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- What cannot be computed locally!
Cited in
(30)- Approximation algorithms for the total dominating set problem
- Near-optimal distributed approximation of minimum-weight connected dominating set
- Distributed verification of minimum spanning trees
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Membrane computing to enhance time efficiency of minimum dominating set
- Structuring unreliable radio networks
- Dominating sets and connected dominating sets in dynamic graphs
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Deterministic distributed construction of T-dominating sets in time T
- Algorithms for the minimum weight k-fold (connected) dominating set problem
- 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
- An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks
- Distributed Dominating Set Approximations beyond Planar Graphs
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Fast primal-dual distributed algorithms for scheduling and matching problems
- An order-based algorithm for minimum dominating set with application in graph mining
- Distributed minimum dominating set approximations in restricted families of graphs
- An efficient distributed algorithm for constructing small dominating sets
- Near-optimal distributed dominating set in bounded arboricity graphs
- A simple distributed algorithm for sparse fractional covering and packing problems
- Deterministic distributed dominating set approximation in the CONGEST model
- Distributed approximation of capacitated dominating sets
- A polynomial-time approximation to a minimum dominating set in a graph
- Distributed algorithms for covering, packing and maximum weighted matching
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
- Distributed MST for constant diameter graphs
- Cellular automata and wireless sensor networks
This page was built for publication: Constant-time distributed dominating set approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5917933)
