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 algorithmad hoc networkfault-tolerantminimum connected dominating setself-stabilizing algorithm

Mathematics Subject Classification ID

Semisimple Lie groups and their representations (22E46) Differential geometry of symmetric spaces (53C35) Distributed systems (68M14) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Noncompact Lie groups of transformations (57S20)

Related Items (5)

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 ⋮ New Self-Stabilizing Algorithms for Minimal Weakly Connected Dominating Sets

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

This page was built for publication: A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET