Sparsifying congested cliques and core-periphery networks

DOI10.1007/978-3-319-48314-6_20MaRDI QIDQ2835033zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• MST in log-star rounds of congested clique
• MST in \(O(1)\) rounds of congested clique
• Distributed computing on core-periphery networks: axiom-based design
• Super-fast MST algorithms in the congested clique using \(o(m)\) messages
• On range and edge capacity in the congested clique

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A faster distributed protocol for constructing a minimum spanning tree
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed computing on core-periphery networks: axiom-based design
• Distributed MST for constant diameter graphs
• Distributed verification and hardness of distributed approximation
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Filling logarithmic gaps in distributed complexity for global problems
• scientific article; zbMATH DE number 1301961 (Why is no real title available?)
• scientific article; zbMATH DE number 1445370 (Why is no real title available?)
• Lessons from the congested clique applied to MapReduce
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• MST in log-star rounds of congested clique
• On the power of the congested clique model
• Optimal deterministic routing and sorting on the congested clique
• Probability and Computing
• Randomized broadcast in networks
• Toward optimal bounds in the congested clique, graph connectivity and MST

Cited in

(2)

• Distributed computing on core-periphery networks: axiom-based design
• On designing networks resilient to clique blockers

This page was built for publication: Sparsifying congested cliques and core-periphery networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835033)