Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs

DOI10.1145/3212734.3212760MaRDI QIDQ5197676zbMATH OpenOpenAlexWikidataFDO

Authors Michal Dory

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.07764

zbMATH Keywords

approximation algorithms\(k\)-edge-connectivitydistributed network design

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Abstract: In the minimum $k$-edge-connected spanning subgraph ($k$-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to $k-1$ edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributed computing community, for $kgeq2$ less is known in the distributed setting. In this paper, we present fast randomized distributed approximation algorithms for $k$-ECSS in the CONGEST model. Our first contribution is an $widetildeO(D+sqrtn)$-round $O(logn)$-approximation for 2-ECSS, for a graph with $n$ vertices and diameter $D$. The time complexity of our algorithm is almost tight and almost matches the time complexity of the MST problem. For larger constant values of $k$ we give an $widetildeO(n)$-round $O(logn)$-approximation. Additionally, in the special case of unweighted 3-ECSS we show how to improve the time complexity to $O(Dlo{g}^{3}n)$ rounds. All our results significantly improve the time complexity of previous algorithms.

Recommendations

• Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
• Near-optimal distributed approximation of minimum-weight connected dominating set
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
• A distributed approximation algorithm for the minimum degree minimum weight spanning trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed minimum dominating set approximations in restricted families of graphs
• Distributed spanner approximation
• Distributed Spanner Approximation

Cited in

(8)

• Fast distributed approximation for TAP and 2-edge-connectivity
• Distributed spanner approximation
• On packing low-diameter spanning trees
• Distributed minimum dominating set approximations in restricted families of graphs
• Finding a small vertex cut on distributed networks
• A distributed algorithm for directed minimum-weight spanning tree
• Stochastic distance in property testing
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms

This page was built for publication: Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197676)