Constant-time distributed dominating set approximation

DOI10.1007/s00446-004-0112-5zbMath1264.68219MaRDI 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

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W15: Distributed algorithms

Related Items

Cellular Automata and Wireless Sensor Networks, Unnamed Item, Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes, Structuring unreliable radio networks, Distributed minimum dominating set approximations in restricted families of graphs, Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem, An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks, Analysing local algorithms in location-aware quasi-unit-disk graphs, Distributed algorithms for covering, packing and maximum weighted matching, 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, A fast network-decomposition algorithm and its applications to constant-time distributed computation, Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs, Deterministic distributed construction of \(T\)-dominating sets in time \(T\), Distributed verification of minimum spanning trees, A polynomial-time approximation to a minimum dominating set in a graph, Fast primal-dual distributed algorithms for scheduling and matching problems, Membrane computing to enhance time efficiency of minimum dominating set, Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation

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!