Fast distributed approximation for TAP and 2-edge-connectivity
From MaRDI portal
Publication:1988524
DOI10.1007/s00446-019-00353-3zbMath1434.68669arXiv1711.03359OpenAlexW2962680238MaRDI QIDQ1988524
Keren Censor-Hillel, Michal Dory
Publication date: 23 April 2020
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.03359
approximation algorithmsconnectivity augmentationdistributed graph algorithmsdistributed network design
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- On the distributional complexity of disjointness
- Approximating node connectivity problems via set covers
- Approximating (unweighted) tree augmentation via lift-and-project. II
- Distributed connectivity decomposition
- Improved distributed steiner forest construction
- Fast computation of small cuts via cycle space sampling
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Approximation Algorithms for Several Graph Augmentation Problems
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Locality in Distributed Graph Algorithms
- Approximation Algorithms for Graph Augmentation
- Biconnectivity approximations and graph carvings
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Distributed Computing: A Locality-Sensitive Approach
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- Distributed Verification and Hardness of Distributed Approximation
- A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
- A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
- A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
- Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- Improved approximation for tree augmentation: saving by rewiring
- Sub-linear distributed algorithms for sparse certificates and biconnected components
- Fast distributed construction of k-dominating sets and applications
- Almost-Tight Distributed Minimum Cut Algorithms
- Efficient distributed approximation algorithms via probabilistic tree embeddings
