Fast Distributed Approximation for TAP and 2-Edge-Connectivity
From MaRDI portal
Publication:3300822
DOI10.4230/LIPIcs.OPODIS.2017.21zbMath1487.68250MaRDI QIDQ3300822
Keren Censor-Hillel, Michal Dory
Publication date: 30 July 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8647/pdf/LIPIcs-OPODIS-2017-21.pdf/
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05C40: Connectivity
68W15: Distributed algorithms
Cites Work
- 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
- 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
- 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