A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs

DOI10.1016/j.tcs.2011.12.007zbMath1285.68017OpenAlexW2043506259MaRDI QIDQ418750

Sayaka Kamei, Hirotsugu Kakugawa

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.007

zbMATH Keywords

self-stabilizationsafe convergencethe minimum connected dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ Self-Stabilizing Domination Algorithms ⋮ New Self-Stabilizing Algorithms for Minimal Weakly Connected Dominating Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Stabilizing phase-clocks
• Stabilization of general loop-free routing
• A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
• Robust self-stabilizing weight-based clustering algorithm
• Unit disk graphs
• A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments
• Distributed algorithms for connected domination in wireless networks
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks
• A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET
• Self-stabilizing systems in spite of distributed control
• Distributed reset
• Simple heuristics for unit disk graphs
• Distributed Computing - IWDC 2003
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Constant-time distributed dominating set approximation