Lessons from the congested clique applied to MapReduce

DOI10.1016/J.TCS.2015.09.029zbMATH Open1333.68277OpenAlexW1863846876MaRDI QIDQ896148FDOQ896148

Authors: James W. Hegeman, Sriram 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

Recommendations

• Lessons from the Congested Clique Applied to MapReduce
• scientific article; zbMATH DE number 6297759
• \((\Delta+1)\) coloring in the congested clique model
• On the power of the congested clique model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

zbMATH Keywords

distributed algorithmsgraph coloringMapReducecongested clique

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• Title not available (Why is that?)
• Distributed Computing with the Cloud
• Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE
• Equivalence classes and conditional hardness in massively parallel computations
• (Delta+1) Coloring in the Congested Clique Model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Lessons from the Congested Clique Applied to MapReduce
• Deterministic Massively Parallel Connectivity
• Distributed PageRank computation with improved round complexities
• Sorting, searching, and simulation in the MapReduce framework
• Sparsifying Congested Cliques and Core-Periphery Networks
• Fast approximate shortest paths in the congested clique
• Congested Clique Algorithms for Graph Spanners
• Title not available (Why is that?)
• Distributed computing with the Cloud

Uses Software

• MapReduce

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

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