A $k$-additive spanner of a graph is a subgraph that preserves the distance between any two nodes up to a total additive error of $+k$. Efficient algorithms have been devised for constructing 2 [Aingworth et al. SIAM '99], 6 [Baswana et al. ACM '10, Woodruff ICALP '13], and 8-additive spanners [Knudsen '17], but efficiency hasn't been studied for 4-additive spanner constructions. In this paper we present a modification of Chechik's 4-additive spanner construction [Chechik SODA '13] that produces a 4-additive spanner on $\widetilde{O}(n^{7/5})$ edges, with an improved runtime of $\widetilde{O}(mn^{3/5})$ from $O(mn)$.


翻译:图表中的一个 $k$- aditive spanterer 是一个子仪, 保存两个节点之间的距离, 直至一个总添加误差为$+k$。 已经设计了高效算法, 用于建造 2 [ Aingworth 等人 SIAM'99] 、 6 [ Baswana 等人 ACM'10, Woodruff icalP'13] 和 8 aditive spanners [ Knudsen'17], 但对于4 aditive spanter 建筑的效率还没有研究。 在本文中, 我们介绍了对Chechik 的 4 adtive spanterner 建筑[ Chechik SIDO'13] 的修改, 该工程在 $\ loblytilde{O} (n ⁇ 7/5} 美元上生产一个4 additive spanterner perates, off $( mn) $( $( mn) $) 。

0
下载
关闭预览

相关内容

第47届自动化、语言和编程国际学术讨论会(ICALP 2020)是欧洲理论计算机科学的主要会议和欧洲理论计算机科学协会(EATCS)年会,将于2020年7月8日至12日在中国北京举行。ICARP 2020将有两个传统的轨道A(算法、复杂度和游戏)和B(自动机、逻辑、语义和编程理论)。官网链接:https://econcs.pku.edu.cn/icalp2020/
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
专知会员服务
61+阅读 · 2020年3月4日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年8月12日
SepNE: Bringing Separability to Network Embedding
Arxiv
3+阅读 · 2019年2月26日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员