Lower Bounds for Maximal Matchings and Maximal Independent Sets
Lower Bounds for Maximal Matchings and Maximal Independent Sets
复制标题
最大匹配和最大独立集的下界
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Suomela
中科院分区：
文献类型：
--
作者：
Alkida Balliu;S. Brandt;J. Hirvonen;Dennis Olivetti;M. Rabie;J. Suomela
有分布式的图算法，用于在O（δ + log^* n）通信回合中找到最大匹配的算法；表明对n的依赖性是最佳的：即使δ= 2，这些问题也无法在o（log^* n）回合中解决。上限和下限之间的指数差距。我们证明上限是紧密的。分布式计算的本地模型作为n的函数，也是对先前的下限的改进。
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log^* n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Δ + log log n / log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Δ + log n / log log n) rounds; this is an improvement over prior lower bounds also as a function of n.
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
小调色板分布式边缘着色的复杂性
DOI：
10.1137/1.9781611975031.168
发表时间：
2018
期刊：
SODA 2018
影响因子：
--
作者：
Chang, Yi-Jun;He, Qizheng;Li, Wenzheng;Pettie, Seth;Uitto, Jara
通讯作者：
Uitto, Jara