Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
ACM Transactions on Algorithms · 31.01.2019 · 15 (1) · 1-29
DOI: 10.1145/3274651 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 16.11.2018. Verfasst von Michael Elkin und 1 weiteren Autor:innen. Die Arbeit wurde bisher 23-mal zitiert (Crossref) und nennt 63 Literaturangaben. Gefördert von: BSF, ISF.
Abstract (Originalsprache)
Miller et al. [48] devised a distributed 1 algorithm in the CONGEST model that, given a parameter k = 1,2,…, constructs an O ( k )-spanner of an input unweighted n -vertex graph with O ( n 1+1/ k ) expected edges in O ( k ) rounds of communication. In this article, we improve the result of Reference [48] by showing a k -round distributed algorithm in the same model that constructs a (2 k −1)-spanner with O ( n 1+1/ k }/ϵ) edges, with probability 1−ϵ for any ϵ>0. Moreover, when k =ω(log n ), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n (1+ o (1)), with probability 1− o (1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that are sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large k , it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for (1+ϵ, β)-spanners and emulators. In particular, we show that for any unweighted n -vertex graph and any ϵ > 0, there exists a (1+ ϵ, (log log n / ϵ) log log n )-emulator with O ( n ) edges. All previous constructions of (1+ϵ, β)-spanners and emulators employ a superlinear number of edges for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths’ computation in unweighted graphs.
Förderung
- BSF
- ISF
Zitieren
APA
Elkin, M., & Neiman, O. (2019). Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Transactions on Algorithms, 15(1), 1-29. https://doi.org/10.1145/3274651
Vancouver
Elkin M, Neiman O. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Transactions on Algorithms. 2019;15(1):1-29. doi:10.1145/3274651
BibTeX
@article{Elkin2019,
author = {Elkin, Michael and Neiman, Ofer},
title = {Efficient Algorithms for Constructing Very Sparse Spanners and Emulators},
journal = {ACM Transactions on Algorithms},
year = {2019},
volume = {15},
number = {1},
pages = {1--29},
doi = {10.1145/3274651}
}
EUVIMED