Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied during the last decade. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of $2\kappa-1$ versus $n^{1+1/\kappa}$, for an integer parameter $\kappa$. (In fact, existing solutions also incur an extra factor of $1+\epsilon$ in the stretch for weighted graphs, and an additional factor of $\log^{O(1)}n$ in the space.) The only existing solution of the second type uses $n^{1/2 - O(1/\kappa)}$ passes over the stream (for space $O(n^{1+1/\kappa})$), and applies only to unweighted graphs. In this paper we show that $(1+\epsilon)$-approximate single-source shortest paths can be computed in this setting with $\tilde{O}(n^{1+1/\kappa})$ space using just \emph{constantly} many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs (assuming $\epsilon$ and $\kappa$ are constant). Moreover, in fact, the same result applies for multi-source shortest paths, as long as the number of sources is $O(n^{1/\kappa})$. We achieve these results by devising efficient dynamic streaming constructions of $(1 + \epsilon, \beta)$-spanners and hopsets. We believe that these constructions are of independent interest.


翻译:在动态流环境中, 近似最短的计算路径是一个根本性的挑战, 在过去十年中已经深入研究过 。 目前, 这个问题的解决方案要么在输入图上构建一个稀多的多倍的扩展范围, 并且计算一个精确的单一源 BFS 树 。 第一类解决方案注定要产生一个2\ kapa-1美元相对于$n ⁇ 1+1/\ kappa}$的伸缩空间交易, 用于一个整数参数 $\ kappa$ 。 ( 事实上, 现有的解决方案在加权图中还产生额外系数$1\\ epslon$, 在空间线外计算一个额外的系数$\ log\\ ol1} 或计算最短的路径 $ 。 第二种类型的解决方案只有$% 2 - O( 1/\\ kappappa)} $( 美元相对于$% 1\\\\ kappappa} 美元, 并且只适用于未加权的图表 。 在本文中, $( 1\ eplon) 美元 美元 美元 和 美元 美元 美元 美元 美元 直径 的原始路径上, 数据 将实现 。

0
下载
关闭预览

相关内容

【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
【经典书】算法C语言实现,Algorithms in C. 672页pdf
专知会员服务
81+阅读 · 2020年8月13日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
5+阅读 · 2017年11月20日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
0+阅读 · 2021年9月23日
VIP会员
相关VIP内容
【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
【经典书】算法C语言实现,Algorithms in C. 672页pdf
专知会员服务
81+阅读 · 2020年8月13日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
5+阅读 · 2017年11月20日
Top
微信扫码咨询专知VIP会员