论文标题
最大独立集的本地计算
Local Computation of Maximal Independent Set
论文作者
论文摘要
我们提供了一种随机局部计算算法（LCA），具有查询复杂性$ poly（δ）\ cdot \ log n $，用于最大独立集（MIS）问题。也就是说，该算法确定每个节点是否在计算的MIS中使用$ poly（δ）\ cdot \ log n $ queries to to Graph的邻接列表，并且具有很高的概率，并且可以同时且独立地对不同的节点进行操作。在这里，$δ$和$ n $表示最高学位和节点的数量。该算法在研究局部计算和sublerear算法（归因于鲁宾菲尔德）的研究中解决了一个关键的开放问题。
We present a randomized Local Computation Algorithm (LCA) with query complexity $poly(Δ) \cdot \log n$ for the Maximal Independent Set (MIS) problem. That is, the algorithm determines whether each node is in the computed MIS or not using $poly(Δ) \cdot \log n$ queries to the adjacency lists of the graph, with high probability, and this can be done for different nodes simultaneously and independently. Here $Δ$ and $n$ denote the maximum degree and the number of nodes. This algorithm resolves a key open problem in the study of local computations and sublinear algorithms (attributed to Rubinfeld).
