Parallel Greedy Spanners
Parallel Greedy Spanners
复制标题
并行贪婪扳手
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Zihan Tan
中科院分区：
文献类型：
--
作者：
Bernhard Haeupler;Ellis Hershkowitz;Zihan Tan
一个图的$t$-子图是一个子图，它的两两距离是$t$-近似的。贪婪算法是构造稀疏边的最简单和最好研究的算法之一：它通过重复选择任何不闭合具有$t+1$或更少边的所选边的循环的边来计算具有$n^{1+O（1/t）}$边的$t$-边。我们证明了贪婪算法计算$t$-t^3 cdot log^3 n cdot n^{1 + O（1/t）}$边，即使这样的边缘匹配是并行添加的。特别地，它足以重复地添加任何匹配，其中每个单独的边缘不闭合具有$t +1 $或更少边缘的循环，但是添加整个匹配可能。我们的分析利用并说明了长度约束扩展分解的新进展的力量。
A $t$-spanner of a graph is a subgraph that $t$-approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a sparse spanner: it computes a $t$-spanner with $n^{1+O(1/t)}$ edges by repeatedly choosing any edge which does not close a cycle of chosen edges with $t+1$ or fewer edges. We demonstrate that the greedy algorithm computes a $t$-spanner with $t^3cdot log^3 n cdot n^{1 + O(1/t)}$ edges even when a matching of such edges are added in parallel. In particular, it suffices to repeatedly add any matching where each individual edge does not close a cycle with $t +1$ or fewer edges but where adding the entire matching might. Our analysis makes use of and illustrates the power of new advances in length-constrained expander decompositions.
DOI：
10.1137/1.9781611977073.129
发表时间：
2022
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Bodwin, Greg;Dinitz, Michael;Robelle, Caleb
通讯作者：
Robelle, Caleb
桥梁周长：网络设计中的统一概念
DOI：
--
发表时间：
2023
期刊：
Proceedings of FOCS (Foundations of Computer Science
影响因子：
--
作者：
Bodwin, G;Trabelsi, O;Hoppenworth, G
通讯作者：
Hoppenworth, G