An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs

DOI10.1016/J.TCS.2015.12.001zbMath1333.68293OpenAlexW2221357966MaRDI QIDQ906392

Tomoko Izumi, Yukiko Yamauchi, Sayaka Kamei

Publication date: 21 January 2016

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

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

zbMATH Keywords

self-stabilizationunit disk graphminimum connected dominating setsafe convergencedistributed approximation algorithmunfair distributed daemon

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (1)

Monotonic self-stabilization and its application to robust and adaptive pattern formation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
• Stabilization of general loop-free routing
• Robust self-stabilizing weight-based clustering algorithm
• Unit disk graphs
• A self-stabilizing algorithm for constructing breadth-first trees
• Distributed algorithms for connected domination in wireless networks
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Survey of local algorithms
• The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction
• 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
• Self-stabilizing systems in spite of distributed control
• Distributed reset
• Simple heuristics for unit disk graphs
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Constant-time distributed dominating set approximation

This page was built for publication: An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs