论文标题
随机$ d $ - 固定度$ D $ D $的大型独立集
Large independent sets on random $d$-regular graphs with fixed degree $d$
论文作者
论文摘要
本文提出了一种线性优先级的本地算法，该算法在随机$ d $的图表上计算大型独立集，该算法具有小和固定度$ D $。我们通过实验研究了算法在[3,100] $中获得的独立比。对于[5,100] $中的所有$ d \，我们的结果大于通过精确方法计算的下限，因此提供了改进的下限估计值。
This paper presents a linear prioritized local algorithm that computes large independent sets on a random $d$-regular graph with small and fixed degree $d$. We studied experimentally the independence ratio obtained by the algorithm when $ d \in [3,100]$. For all $d \in [5,100]$, our results are larger than lower bounds calculated by exact methods, thus providing improved estimates of lower bounds.
