Move Complexity of a Self-Stabilizing Algorithm for Maximal Independent Sets

03/25/2022

∙

by   Volker Turau, et al.

∙

0

∙

share

A_𝖽𝖾𝗀 is a self-stabilizing algorithm that computes a maximal independent set in a finite graph with approximation ratio (Δ + 2)/3. In this note we show that under the central scheduler the number of moves of A_𝖽𝖾𝗀 is not bounded by a polynomial in n.