Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

被引：3

作者：

Bezdrighin, Marcel ^{[1
]}

Elkin, Michael ^{[2
]}

Ghaffari, Mohsen ^{[1
]}

Grunau, Christoph ^{[1
]}

Haeupler, Bernhard ^{[1
,3
]}

Ilchi, Saeed ^{[1
]}

Rozhon, Vaclav ^{[1
]}

机构：

[1] Swiss Fed Inst Technol, Zurich, Switzerland

[2] Ben Gurion Univ Negev, Beer Sheva, Israel

[3] Carnegie Mellon Univ, Pittsburgh, PA USA

来源：

PROCEEDINGS OF THE 34TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2022 | 2022年

基金：

欧洲研究理事会;

关键词：

Distributed Computing; Spanners; Ultra-Sparse Spanners; LowDiameter Clustering; Connectivity Certificates; DECOMPOSITION; CONSTRUCTIONS; ALGORITHM; DIAMETER;

D O I：

10.1145/3490148.3538565

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: circle We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in polylog(n) rounds in weighted graphs. Concretely, our algorithm outputs a spanning subgraph with only n +o (n) edges in which the pairwise distances are stretched by a factor of at most O ( log n center dot 2(O (log*n))). circle We provide a polylog(n)-round deterministic distributed algorithm that computes a spanner with stretch (2k - 1) and O (nk +n(1+1/k) logk) edges in unweighted graphs and with O(n(1+1/k)k) edges in weighted graphs. circle We present the first polylog(n) round randomized distributed algorithm that computes a sparse connectivity certificate. For an n-node graph G, a certificate for connectivity kappa is a spanning subgraph H that is kappa-edge-connected if and only if G is kappa-edge-connected, and this subgraph.. is called sparse if it has O(nk) edges. Our algorithm achieves a sparsity of (1 +o (1))nk edges, which is within a 2(1 +o(1)) factor of the best possible.

引用

页码：1 / 10

页数：10

共 55 条

[1] The 4/3 Additive Spanner Exponent Is Tight [J].