Linear-Time Self-Stabilizing Algorithms for Disjoint Independent Sets

摘要

A set S of nodes in a graph G = (V, E) is independent if no two nodes in S are adjacent. We present two types of self-stabilizing algorithms for finding disjoint independent sets R and B. In one type, R is maximal independent in G and B is maximal independent in the induced subgraph G[V - R]. In the second type, R is maximal independent in G[V - B] and B is maximal independent in G[V - R]. Both the central and distributed schedulers are considered.