Constant-time distributed dominating set approximation

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

Mathematics Subject Classification ID

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

• 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!
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Constant-time distributed dominating set approximation