Local Computation Algorithms for Graphs of Non-constant Degrees
Local Computation Algorithms for Graphs of Non-constant Degrees
复制标题
非常数度图的局部计算算法
DOI：
10.1007/s00453-016-0126-y
复制
发表时间：
2017
期刊：
影响因子：
1.1
通讯作者：
Yodpinyanee, Anak
中科院分区：
文献类型：
--
作者：
Levi, Reut;Rubinfeld, Ronitt;Yodpinyanee, Anak
在局部计算算法（LCA）模型中，我们的目标是通过仅检查输入的一小部分（次线性）来计算输出的查询部分。 LCA 的这一关键方面概括了各种其他模型，例如并行算法、局部滤波器和重构器。对于图问题，LCA 的设计技术和分布式算法密切相关，并且已被证明在彼此的上下文中都很有用。许多最近开发的针对图问题的 LCA 实现了时间和空间复杂性，并且对 n（顶点数）的依赖性非常低。尽管如此，这些复杂性通常至少在 d（输入图度数的上限）上呈指数关系。我们考虑参数 d 可以适度依赖于 n 的情况，并以对 d 具有次指数依赖的复杂性为目标，同时保持对 n 的多对数依赖。我们提出：一种用于计算最大独立集的随机 LCA，其时间和空间复杂度是 d 和多对数 inn 中的拟多项式；对于常数 eps > 0，随机 LCA 提供高概率最大匹配的 (1-ε) 近似，其时间和空间复杂度为多项式 ind 和多对数 inn。
In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. This key aspect of LCAs generalizes various other models such as parallel algorithms, local filters and reconstructors. For graph problems, design techniques for LCAs and distributed algorithms are closely related and have been proven useful in each other's context. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. We consider the case where the parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence ond, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic inn; for constant eps > 0, a randomized LCA that provides a (1-ε)-approximation to maximum matching with high probability, whose time and space complexities are polynomial indand polylogarithmic inn.
登录
查看更多内容
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
DOI：
10.1002/rsa.3240020402
发表时间：
1991-12
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
J. Beck
通讯作者：
J. Beck
近似有界度和一般稀疏图中属性的距离
DOI：
10.1145/1497290.1497298
发表时间：
2009
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
S. Marko;D. Ron
通讯作者：
D. Ron
当地财产恢复
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
Zvika Brakerski
通讯作者：
Zvika Brakerski
连接性和直径的本地重构器和容差测试器
DOI：
--
发表时间：
2012
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Andrea Campagna;Alan J. X. Guo;R. Rubinfeld
通讯作者：
R. Rubinfeld