Sparsifying Congested Cliques and Core-Periphery Networks

DOI10.1007/978-3-319-48314-6_20zbMath1482.68045OpenAlexW2548025525MaRDI QIDQ2835033

Alkida Balliu, Pierre Fraigniaud, Zvi Lotker, Dennis Olivetti

Publication date: 1 December 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48314-6_20

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lessons from the congested clique applied to MapReduce
• On fast and robust information spreading in the vertex-congest model
• Algebraic methods in the congested clique
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Toward Optimal Bounds in the Congested Clique
• On the power of the congested clique model
• Randomized broadcast in networks
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing on Core-Periphery Networks: Axiom-Based Design
• Filling Logarithmic Gaps in Distributed Complexity for Global Problems
• Optimal deterministic routing and sorting on the congested clique
• MST in Log-Star Rounds of Congested Clique
• Distributed verification and hardness of distributed approximation
• Probability and Computing
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Distributed MST for constant diameter graphs