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

DOI10.1016/J.TCS.2011.12.007MaRDI QIDQ418750zbMATH OpenOpenAlexFDO

Authors 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

safe convergenceself-stabilizationthe minimum connected dominating set

Mathematics Subject Classification ID

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

Recommendations

• An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
• A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
• Self-stabilizing algorithm for minimal dominating set with safe convergence in an arbitrary graph
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• New self-stabilizing algorithms for minimal weakly connected dominating sets

Cites work

• A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
• A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
• A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Constant-time distributed dominating set approximation
• Distributed algorithms for connected domination in wireless networks
• Distributed Computing - IWDC 2003
• Distributed reset
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 1332668 (Why is no real title available?)
• scientific article; zbMATH DE number 2061544 (Why is no real title available?)
• scientific article; zbMATH DE number 2061548 (Why is no real title available?)
• scientific article; zbMATH DE number 2209525 (Why is no real title available?)
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Robust self-stabilizing weight-based clustering algorithm
• Self-stabilization
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing systems in spite of distributed control
• Simple heuristics for unit disk graphs
• Stabilization of general loop-free routing
• Stabilizing phase-clocks
• Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks
• Unit disk graphs

Cited in

(4)

• Self-Stabilizing Domination Algorithms
• A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
• New self-stabilizing algorithms for minimal weakly connected dominating sets
• An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs

This page was built for publication: A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418750)