Fast distributed approximation for TAP and 2-edge-connectivity
From MaRDI portal
Publication:3300822
DOI10.4230/LIPICS.OPODIS.2017.21zbMATH Open1487.68250OpenAlexW2945402626MaRDI QIDQ3300822FDOQ3300822
Authors: 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/
Recommendations
- Fast distributed approximation for TAP and 2-edge-connectivity
- Brief announcement: Distributed approximation for tree augmentation
- A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- LP-relaxations for tree augmentation
- Covering a laminar family by leaf to leaf links
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40) Distributed algorithms (68W15)
Cites Work
- Approximation algorithms for NP-hard problems.
- Title not available (Why is that?)
- Fast computation of small cuts via cycle space sampling
- Distributed Computing: A Locality-Sensitive Approach
- Distributed verification and hardness of distributed approximation
- Biconnectivity approximations and graph carvings
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Locality in Distributed Graph Algorithms
- A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- 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 SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Approximation Algorithms for Graph Augmentation
- Fast distributed construction of k-dominating sets and applications
- Approximation Algorithms for Several Graph Augmentation Problems
- Almost-Tight Distributed Minimum Cut Algorithms
- Sub-linear distributed algorithms for sparse certificates and biconnected components
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Improved distributed steiner forest construction
- Efficient distributed approximation algorithms via probabilistic tree embeddings
Cited In (3)
This page was built for publication: Fast distributed approximation for TAP and 2-edge-connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300822)
