A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

DOI10.1137/S0097539794261118zbMath0911.05052OpenAlexW2163097371MaRDI QIDQ4388873

Shay Kutten, Juan A. Garay, David Peleg

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794261118

zbMATH Keywords

MSTtime complexitydistributed network algorithmsmin-weight spanning treesminimum-weight spanning tree algorithm

Mathematics Subject Classification ID

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 (29)

Latency, capacity, and distributed minimum spanning trees ⋮ TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ Exact Bounds for Distributed Graph Colouring ⋮ Unnamed Item ⋮ Low-congestion shortcuts without embedding ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Sublinear fully distributed partition with applications ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ A linear-time optimal-message distributed algorithm for minimum spanning trees ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Low-congestion shortcut and graph parameters ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ On the Microscopic View of Time and Messages ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Distributed MST for constant diameter graphs ⋮ Labeling schemes for tree representation ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ A distributed algorithm to find \(k\)-dominating sets ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Unnamed Item ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees