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) $) 。
相关内容
微信扫码咨询专知VIP会员