Article ID Journal Published Year Pages File Type
428190 Information Processing Letters 2007 6 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics