A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET

DOI10.1142/S0129054110007362zbMath1192.68847MaRDI QIDQ3569287

Sayaka Kamei, Hirotsugu Kakugawa

Publication date: 18 June 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation algorithm; ad hoc network; fault-tolerant; minimum connected dominating set; self-stabilizing algorithm

Mathematics Subject Classification ID

22E46: Semisimple Lie groups and their representations

53C35: Differential geometry of symmetric spaces

68M14: Distributed systems

68W25: Approximation algorithms

68M15: Reliability, testing and fault tolerance of networks and computer systems

68W15: Distributed algorithms

57S20: Noncompact Lie groups of transformations

Related Items

New Self-Stabilizing Algorithms for Minimal Weakly Connected Dominating Sets, A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs, Timer-based composition of fault-containing self-stabilizing protocols, Self-Stabilizing Domination Algorithms

Cites Work

• Unnamed Item
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Unit disk graphs
• A self-stabilizing algorithm for constructing breadth-first trees
• A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Self-stabilizing systems in spite of distributed control
• Simple heuristics for unit disk graphs