Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE

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

zbMATH Keywords

Steiner treedistributed approximation algorithmCONGESTED CLIQUEshortest path forest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (1)

The Clustered Selected-Internal Steiner Tree Problem

Uses Software

• MapReduce

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