Fast distributed approximation for TAP and 2-edge-connectivity

DOI10.4230/LIPICS.OPODIS.2017.21MaRDI QIDQ3300822zbMATH OpenOpenAlexFDO

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/

zbMATH Keywords

approximation algorithmsconnectivity augmentationdistributed network design

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40) Distributed algorithms (68W15)

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

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• 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
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Almost-Tight Distributed Minimum Cut Algorithms
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation algorithms for NP-hard problems.
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Biconnectivity approximations and graph carvings
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Fast computation of small cuts via cycle space sampling
• Fast distributed construction of k-dominating sets and applications
• Improved distributed Steiner forest construction
• Locality in Distributed Graph Algorithms
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Sub-linear distributed algorithms for sparse certificates and biconnected components

Cited in

(3)

• 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

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)