Lessons from the congested clique applied to MapReduce

DOI10.1016/j.tcs.2015.09.029zbMath1333.68277OpenAlexW1863846876MaRDI QIDQ896148

James W. Hegeman, Sriram V. Pemmaraju

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.09.029

zbMATH Keywords

graph coloringdistributed algorithmsMapReducecongested clique

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (12)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Deterministic Massively Parallel Connectivity ⋮ Distributed computing with the Cloud ⋮ Distributed PageRank computation with improved round complexities ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE

Uses Software

• MapReduce

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Simple distributed \(\Delta+1\)-coloring of graphs
• Algebraic methods in the congested clique
• Toward Optimal Bounds in the Congested Clique
• The communication complexity of distributed task allocation
• The round complexity of distributed sorting
• On the power of the congested clique model
• Super-Fast 3-Ruling Sets.
• Super-Fast Distributed Algorithms for Metric Facility Location
• A Distributed Algorithm for the Facility Location Problem
• A Plant and Warehouse Location Problem
• Distributed Computing: A Locality-Sensitive Approach
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• Return of the primal-dual
• Optimal deterministic routing and sorting on the congested clique
• Rapid randomized pruning for fast greedy distributed algorithms
• Facility location
• Distributed approximation algorithms for weighted shortest paths
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Distributed MST for constant diameter graphs

This page was built for publication: Lessons from the congested clique applied to MapReduce