A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O ( n m A ) moves, where A is t...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2009-06, Vol.109 (14), p.763-767
Main Authors: Turau, Volker, Hauck, Bernd
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Computer systems performance. Reliability
Distributed algorithms
Exact sciences and technology
Fault tolerance
Graph algorithms
Graph theory
Mathematics
Miscellaneous
Sciences and techniques of general use
Self-stabilizing algorithms
Software
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O ( n m A ) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2009.03.013