.png){kind=icon}
.png){kind=icon}
Return
Self-Stabilizing Algorithm for Multiple Disjoint Maximal Independent Sets
.png){kind=icon}
OA
AI
DOI：10.1007/s44227-025-00082-z.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Self-stabilizing algorithm
Maximal independent set
Distributed system
Network
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
0.5
Papers:
30
Citations:
94