Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler |
| |
| Authors: | Volker Turau |
| |
| Affiliation: | Hamburg University of Technology, Institute of Telematics, Schwarzenbergstraße 95, 21073 Hamburg, Germany |
| |
| Abstract: | This paper presents distributed self-stabilizing algorithms for the maximal independent and the minimal dominating set problems. Using an unfair distributed scheduler the algorithms stabilizes in at most max{3n−5,2n} resp. 9n moves. All previously known algorithms required O(n2) moves. |
| |
| Keywords: | Self-stabilizing algorithms Fault tolerance Distributed computing Graph algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
