A distributed algorithm for directed minimum-weight spanning tree

DOI10.4230/LIPICS.DISC.2019.16MaRDI QIDQ6487532zbMATH OpenFDO

Authors Orr Fischer, Rotem Oshman

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2019.16

zbMATH Keywords

distributed computingdirected minimum spanning treeCONGESTminimum arborescence

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

Cited in

(7)

• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• Updating Directed Minimum Cost Spanning Trees
• From sequential layers to distributed processes
• Single-source shortest paths in the CONGEST model with improved bounds
• Distributed planar reachability in nearly optimal time
• A distributed algorithm for directed minimum-weight spanning tree
• An efficient distributed algorithm for centering a spanning tree of a biconnected graph

This page was built for publication: A distributed algorithm for directed minimum-weight spanning tree

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