Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE
From MaRDI portal
Publication:5859656
DOI10.1142/S0129054120500367zbMath1458.68278arXiv1907.12011OpenAlexW2966268726MaRDI QIDQ5859656
Sushanta Karmakar, Parikshit Saikia
Publication date: 19 April 2021
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.12011
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A distributed O(1)-approximation algorithm for the uniform facility location problem
- Lessons from the congested clique applied to MapReduce
- The Steiner tree problem on graphs: inapproximability results
- A fast algorithm for Steiner trees
- The Steiner problem in distributed computing systems
- A fast distributed approximation algorithm for minimum spanning trees
- Algebraic methods in the congested clique
- Efficient determination of the transitive closure of a directed graph
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Toward Optimal Bounds in the Congested Clique
- Fast Partial Distance Estimation and Applications
- An improved LP-based approximation for steiner tree
- The communication complexity of distributed task allocation
- The round complexity of distributed sorting
- On the power of the congested clique model
- Super-Fast Distributed Algorithms for Metric Facility Location
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages
- “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
- Reducibility among Combinatorial Problems
- Proof-Labeling Schemes: Broadcast, Unicast and in Between
- Fast Approximate Shortest Paths in the Congested Clique
- Connectivity Lower Bounds in Broadcast Congested Clique
- Optimal deterministic routing and sorting on the congested clique
- Distributed approximation algorithms for weighted shortest paths
- MST in Log-Star Rounds of Congested Clique
- Distributed Computation of Large-scale Graph Problems
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Computing and Combinatorics
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- A faster approximation algorithm for the Steiner problem in graphs
This page was built for publication: Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE
