Local Computation of Maximal Independent Set
Local Computation of Maximal Independent Set
复制标题
最大独立集的局部计算
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Ghaffari
中科院分区：
文献类型：
--
作者：
M. Ghaffari
针对最大独立集（MIS）问题，提出了一个查询复杂度为poly $（Delta）cdot log n$的随机局部计算算法（LCA）.也就是说，该算法确定每个节点是否在计算的MIS或不使用聚$（三角洲）cdotlog n$查询的邻接表的图形，具有很高的概率，这可以同时和独立地为不同的节点。这里$Delta$和n表示最大度和节点数。该算法解决了局部计算和次线性算法研究中的一个关键公开问题（归因于Rubinfeld）。
We present a randomized Local Computation Algorithm (LCA) with query complexity poly $(Delta) 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 $(Delta)cdotlog n$ queries to the adjacency lists of the graph, with high probability, and this can be done for different nodes simultaneously and independently. Here $Delta$ 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).
DOI：
10.1137/1.9781611976465.172
发表时间：
2021-01
期刊：
--
影响因子：
--
作者：
M. Ghaffari;Bernhard Haeupler
通讯作者：
M. Ghaffari;Bernhard Haeupler
影响因子：
1.1
作者：
Levi, Reut;Rubinfeld, Ronitt;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak