New Additive Spanners
New Additive Spanners
复制标题
新型增材扳手
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Chechik
中科院分区：
文献类型：
--
作者：
S. Chechik
本文考虑了添加剂和纯粹的添加剂。大小O（N3/2）的跨度，另一个用于6个大小O（N4/3）的跨度，因此在此区域中回答了一个主要的开放问题。对于任何3/17≤Δ<1/3，N1+δ）边缘和O（N1/2-3δ/2）的添加剂伸展−3δ）。 ）。
This paper considers additive and purely additive spanners. We present a new purely additive spanner of size O(n7/5) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for 2-additive spanner of size O(n3/2) and the other for 6-additive spanner of size O(n4/3), and thus answers a main open question in this area. In addition, we present a construction for additive spanners with O(n1+δ) edges and additive stretch of O(n1/2−3δ/2) for any 3/17 ≤ δ < 1/3, improving the stretch of the existing constructions from O(n1−3δ) to O(√n1−3δ). Finally, we show that our (1,n1/2−3δ/2)-spanner construction can be tweaked to give a sublinear additive spanner of size O(n1+3/17) with additive stretch O(√distance).