Distributed Computation of Large-scale Graph Problems

DOI10.1137/1.9781611973730.28zbMath1371.68214arXiv1311.6209OpenAlexW2950274216MaRDI QIDQ5362982

Peter Robinson, Hartmut Klauck, Gopal Pandurangan, Danupon Nanongkai

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.6209

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network protocols (68M12) Distributed algorithms (68W15)

Related Items

Equivalence classes and conditional hardness in massively parallel computations ⋮ Graph reconstruction in the congested clique ⋮ Distributed PageRank computation with improved round complexities ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ 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 ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Near-optimal scheduling in the congested clique