A self-stabilizing algorithm for constructing weakly connected minimal dominating sets |
| |
Authors: | Volker Turau Bernd Hauck |
| |
Affiliation: | Hamburg University of Technology, Institute of Telematics, Schwarzenbergstraße 95, 21073 Hamburg, Germany |
| |
Abstract: | 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(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves. |
| |
Keywords: | Self-stabilizing algorithms Fault tolerance Distributed algorithms Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |