Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
From MaRDI portal
Publication:5700572
DOI10.1137/S0097539704441848zbMath1082.05522OpenAlexW1987099434MaRDI QIDQ5700572
Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, David Peleg
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704441848
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (37)
Local MST computation with short advice ⋮ Graph reconstruction in the congested clique ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Lessons from the congested clique applied to MapReduce ⋮ Fault-tolerant graph realizations in the congested clique ⋮ Distributed computing with the Cloud ⋮ Exact distributed sampling ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Distributed CONGEST Algorithms against Mobile Adversaries ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Analysis of randomized protocols for conflict-free distributed access ⋮ Randomized proof-labeling schemes ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Microscopic View of Time and Messages ⋮ Message lower bounds via efficient network synchronization ⋮ The role of randomness in the broadcast congested clique model ⋮ Sub-logarithmic distributed algorithms for metric facility location ⋮ Distributed MST for constant diameter graphs ⋮ The Impact of Locality in the Broadcast 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 ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Breaking the \(\log n\) barrier on rumor spreading ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Near-optimal scheduling in the congested clique ⋮ Approximate minimum directed spanning trees under congestion
This page was built for publication: Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
