Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

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(n(2)) moves. (c) 2007 Elsevier B.V. All rights reserved.