MIS on trees
MIS on trees
复制标题
树木管理信息系统
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
Christoph Lenzen;Roger Wattenhofer
图上的极大独立集是互不相邻节点的包含极大集。这种基本的对称性破缺结构对于许多分布式算法至关重要，几十年来，它一直在推动寻找快速局部算法来找到这样的集合。在本文中，我们提出了一个解决方案，随机运行时间为O（log n log log n）的树，提高了约二次方的最先进的界限。我们的算法是统一的，节点只需要交换O（log n）许多位的高概率。与以前的技术实现亚对数运行时间相比，我们的方法不依赖于任何独立邻居的数量上的限制（可能是关于边缘的方向）。
A maximal independent set on a graph is an inclusion-maximal set of mutually non-adjacent nodes. This basic symmetry breaking structure is vital for many distributed algorithms, which by now has been fueling the search for fast local algorithms to find such sets over several decades. In this paper, we present a solution with randomized running time O(√log n log log n) on trees, improving roughly quadratically on the state-of-the-art bound. Our algorithm is uniform and nodes need to exchange merely O(log n) many bits with high probability. In contrast to previous techniques achieving sublogarithmic running times, our approach does not rely on any bound on the number of independent neighbors (possibly with regard to an orientation of the edges).