Constant-time distributed dominating set approximation
From MaRDI portal
Publication:5917933
DOI10.1007/s00446-004-0112-5zbMath1264.68219OpenAlexW3083234306MaRDI QIDQ5917933
Fabian Kuhn, Roger Wattenhofer
Publication date: 7 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/32917
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)
Related Items (20)
A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Membrane computing to enhance time efficiency of minimum dominating set ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Distributed verification of minimum spanning trees ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Unnamed Item ⋮ Cellular Automata and Wireless Sensor Networks ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Structuring unreliable radio networks ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks ⋮ An order-based algorithm for minimum dominating set with application in graph mining
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Approximation algorithms for connected dominating sets
- Discrete mobile centers
- A threshold of ln n for approximating set cover
- A Greedy Heuristic for the Set-Covering Problem
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- A parallel approximation algorithm for positive linear programming
- What cannot be computed locally!
This page was built for publication: Constant-time distributed dominating set approximation
