Fast deterministic distributed algorithms for sparse spanners
- 作者：Bilel Derbel ; Cyril Gavoille
- 关键词：Distributed algorithms ; Graph spanners ; Time complexity ; Linial’ ; s free model
- 刊名：Theoretical Computer Science
- 出版年：2008
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：3 June 2008
- 卷：399
- 期：1-2
- 页码：83-100
- 文件大小：1156 K
摘要
This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with 17b500d8e777f19e98c0624ac" title="Click to view the MathML source" alt="Click to view the MathML source">n nodes. All previous deterministic distributed algorithms, for constant stretch spanners of b67b1964d97f" title="Click to view the MathML source" alt="Click to view the MathML source">o(n2) edges, have a running time Ω(n
) for some constant >0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n2) edges in o(n) time for any constant >0.
) for some constant >0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n2) edges in o(n) time for any constant >0.