Optimal deterministic routing and sorting on the congested clique
From MaRDI portal
Publication:5176081
DOI10.1145/2484239.2501983zbMath1323.68034arXiv1207.1852OpenAlexW2139535340MaRDI QIDQ5176081
Publication date: 2 March 2015
Published in: Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.1852
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14)
Related Items (29)
Tight bounds for parallel randomized load balancing ⋮ Graph reconstruction in the congested clique ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Lessons from the congested clique applied to MapReduce ⋮ Distributed coloring of hypergraphs ⋮ Distributed PageRank computation with improved round complexities ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? ⋮ Round Compression for Parallel Matching Algorithms ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Algebraic methods in the congested clique ⋮ Reliable communication over highly connected noisy networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ Message lower bounds via efficient network synchronization ⋮ Sub-logarithmic distributed algorithms for metric facility location ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Fast approximate shortest paths in the congested clique ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC ⋮ Near-optimal scheduling in the congested clique
This page was built for publication: Optimal deterministic routing and sorting on the congested clique
