A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
From MaRDI portal
Publication:2706118
DOI10.1137/S0097539700369740zbMath0973.05074OpenAlexW2015819397MaRDI QIDQ2706118
Vitaly Rubinovich, David Peleg
Publication date: 19 March 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700369740
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (36)
Latency, capacity, and distributed minimum spanning trees ⋮ Distributed Broadcast Revisited: Towards Universal Optimality ⋮ Low-congestion shortcuts without embedding ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Distributed distance computation and routing with small messages ⋮ Minimum cost flow in the CONGEST model ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Constructing near spanning trees with few local inspections ⋮ Sublinear fully distributed partition with applications ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Hundreds of impossibility results for distributed computing ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ On the complexity of distributed stable matching with small messages ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Low-congestion shortcut and graph parameters ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ Algebraic methods in the congested clique ⋮ Fast protocols for leader election and spanning tree construction in a distributed network ⋮ Compact distributed certification of planar graphs ⋮ Message lower bounds via efficient network synchronization ⋮ Local algorithms for sparse spanning graphs ⋮ Distributed MST for constant diameter graphs ⋮ 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 Spanner Approximation ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Unnamed Item ⋮ Local certification of graphs with bounded genus ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Distributed communication complexity of spanning tree construction ⋮ Approximate minimum directed spanning trees under congestion
This page was built for publication: A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
