Fast distributed approximation for TAP and 2-edge-connectivity

DOI10.1007/s00446-019-00353-3zbMath1434.68669arXiv1711.03359MaRDI 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

zbMATH Keywords

approximation algorithms; connectivity augmentation; distributed graph algorithms; distributed network design

Mathematics Subject Classification ID

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
• 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