Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics
Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics
复制标题
简短公告：双倍度量单位球图的分布式轻量级 Spanner 构造
DOI：
10.1145/3490148.3538553
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Khodabandeh, Hadi
中科院分区：
文献类型：
--
作者：
Eppstein, David;Khodabandeh, Hadi
解决了2006年提出的一个公开问题，证明了单位球图在有界双倍维数度量下存在轻量有界度（1+ε）-空间，并在该空间模型下设计了一个简单的O（log*n）轮分布式算法，仅利用2跳邻域信息寻找该空间.我们进一步研究了二维欧氏平面上的问题，并提出了一个具有类似性质的结构，它也具有低交性质。最后，我们提供了实验结果，证实了我们的算法的性能。
Resolving an open question from 2006, we prove the existence of light-weight bounded-degree (1+ε)-spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple O(log*n)-round distributed algorithm in the LOCAL model for finding such spanners using only 2-hop neighborhood information. We further study the problem in the two dimensional Euclidean plane and we propose a construction with similar properties that has a low-intersection property as well. Lastly, we provide experimental results that confirm the performance of our algorithms.
登录
查看更多内容
DOI：
10.1137/s0097539700382947
发表时间：
2002-05
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
通讯作者：
Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
DOI：
--
发表时间：
2019
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Michael Elkin;Arnold Filtser;Ofer Neiman
通讯作者：
Ofer Neiman
DOI：
--
发表时间：
2020
期刊：
International Symposium on Computational Geometry
影响因子：
--
作者：
D. Eppstein;Hadi Khodabandeh
通讯作者：
Hadi Khodabandeh
加倍度量空间中的分布式 Spanner 构造
DOI：
--
发表时间：
2006
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
Mirela Damian;Saurav Pandit;Sriram V. Pemmaraju
通讯作者：
Sriram V. Pemmaraju
本地计算轻量级 Spanner
DOI：
--
发表时间：
2008
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
Iyad A. Kanj;Ljubomir Perković;Ge Xia
通讯作者：
Ge Xia