Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
复制标题
（近）线性时间内一般图的近最优 Spanner
DOI：
10.1137/1.9781611977073.132
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Solomon, Shay
中科院分区：
文献类型：
--
作者：
Le, Hung;Solomon, Shay
设G =（V，E，w）是上的一个加权无向图，|V| = n个顶点，|E| = medges，设k ≥ 1为任意整数，设k < 1为任意参数。我们提出了以下结果，快速构建spectrometry与接近最佳的稀疏度和亮度，1这是一个长期的工作在这一领域的高潮。（近似最优的意思是在Erdos'围长猜想下的最优的，并且不考虑依赖性。有（确定性）算法可以构造G的（2k-1）（1 + k）-空间，其近似最优稀疏度为O（n1/k· log（1/k）/k））。第一个算法在指针机器模型中可以在时间O（mα（m，n）· log（1/n）/n）+ SORT（m））内实现，其中α（·，·）是两参数逆Ackermann函数，SORT（m）是排序器所需的时间.第二个算法可以在Word RAM模型中实现，时间为O（mlog（1/k）/n））。有一个（确定性）算法可以构造G的（2k-1）（1 + k）-k，该算法在稀疏度和亮度上都达到O（n1/k·poly（1/k））的近最优界。该算法在指针机模型和Word RAM模型中的实现时间分别为O（m α（m，n）· poly（1/n）+ SORT（m））和O（mα（m，n）· poly（1/n）），而在（2k-1）（1 + n）-spectrometry中，即使不考虑亮度，其最快的构造时间也为isO（min{m（n1+1/k）+nlogn，k·n2+1/k}）.重要的是，2k-1段的贪婪生成器具有稀疏性O（n1/k）-没有任何依赖性，但它的运行时间是O（m（n1+1/k+nlogn））。此外，任何（2k-1）-bandwidth（包括贪婪bandwidth）的最新亮度界限都很差，即使不考虑稀疏性和运行时间。
LetG= (V, E, w) be a weighted undirected graph on |V| = nvertices and |E| = medges, letk≥ 1 be any integer, and let∊< 1 be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness,1which culminate a long line of work in this area. (Bynear-optimalwe mean optimal under Erdos' girth conjecture and disregarding the∊-dependencies.)There are (deterministic) algorithms for constructing (2k–1)(1 +∊)-spanners forGwith a near-optimal sparsity ofO(n1/k· log(1/∊)/∊)). The first algorithm can be implemented in the pointer-machine model within timeO(mα(m, n) · log(1/∊)/∊)+ SORT(m)), whereα(·,·) is the two-parameter inverse-Ackermann function and SORT(m) is the time needed to sortmintegers. The second algorithm can be implemented in the Word RAM model within timeO(mlog(1/∊)/∊)).There is a (deterministic) algorithm for constructing a (2k–1)(1 +∊)-spanner forGthat achieves a near-optimal bound ofO(n1/k·poly(1/∊)) on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within timeO(mα(m,n) · poly(1/∊) + SORT(m)) and in the Word RAM model within timeO(mα(m,n) · poly(1/∊)).The previous fastest constructions of (2k–1)(1 +∊)-spanners with near-optimal sparsity incur a runtime of isO(min{m(n1+1/k) +nlogn, k·n2+1/k}), even regardless of the lightness. Importantly, thegreedy spannerfor stretch 2k–1 has sparsityO(n1/k) — with no∊-dependence whatsoever, but its runtime isO(m(n1+1/k+nlogn)). Moreover, the state-of-the-art lightness bound of any (2k–1)-spanner (including the greedy spanner) is poor, even regardless of the sparsity and runtime.
登录
查看更多内容
DOI：
--
发表时间：
2005
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
L. Roditty;M. Thorup;Uri Zwick
通讯作者：
Uri Zwick
影响因子：
0.5
作者：
B. Awerbuch
通讯作者：
B. Awerbuch
计算加权图中 O(n1 1/k) 大小的 (2k-1)-Spanner 的简单线性时间算法
DOI：
--
发表时间：
2003
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Surender Baswana;Sandeep Sen
通讯作者：
Sandeep Sen
具有较小路由成本的光图
影响因子：
2.1
作者：
B. Wu;K. Chao;C. Tang
通讯作者：
C. Tang
近乎最佳的轻型扳手
DOI：
10.1145/3199607
发表时间：
2016
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
S. Chechik;Christian Wulff
通讯作者：
Christian Wulff