论文标题
移动最大独立集的自动化算法的复杂性
Move Complexity of a Self-Stabilizing Algorithm for Maximal Independent Sets
论文作者
论文摘要
$ {\ cal a} _ \ mathsf {deg} $是一种自动化算法，该算法计算具有近似值$（δ+ 2）/3 $的有限图中的最大独立集。在本说明中，我们表明，在中央调度程序下，$ {\ cal a} _ \ mathsf {deg} $的移动次数不受$ n $中的多项式的界限。
${\cal A}_\mathsf{deg}$ 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 ${\cal A}_\mathsf{deg}$ is not bounded by a polynomial in $n$.
