Self-Stabilizing Algorithm for Multiple Disjoint Maximal Independent Sets

Abstract

This paper presents a self-stabilizing algorithm for computing multiple disjoint maximal independent sets in a graph. The first set is a maximal independent set in the entire graph, the second set is a maximal independent set in the subgraph formed by removing the nodes in the first independent set, and each subsequent set is computed similarly by excluding the nodes from all previous sets. The algorithm introduces a novel method by using a single local integer variable for each node to determine its membership in a specific independent set, offering a more efficient solution compared to earlier methods. Additionally, this algorithm provides an upper bound on the chromatic number required for the graph coloring problem. The solution is developed under the central daemon model and guarantees termination after a finite number of moves.