The distributed minimum spanning tree problem

MaRDI QIDQ5203926zbMATH OpenFDO

Authors Gopal Pandurangan, Peter Robinson, Michele Scquizzato

Publication date 9 December 2019

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/538/538

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
• Distributed MST for constant diameter graphs

Cited in

(16)

• The Steiner problem in distributed computing systems
• Approximate minimum directed spanning trees under congestion
• Latency, capacity, and distributed minimum spanning trees
• Low-congestion shortcut and graph parameters
• Sparse matrix multiplication and triangle listing in the congested clique model
• A note on improved results for one round distributed clique listing
• A distributed algorithm for directed minimum-weight spanning tree
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• Optimal cost-sensitive distributed minimum spanning tree algorithm
• Time-message trade-offs in distributed algorithms
• Sparse matrix multiplication and triangle listing in the congested clique model
• The shared broadcast tree problem and MST
• Filling logarithmic gaps in distributed complexity for global problems
• Brief announcement: Distributed approximation for tree augmentation
• Distributed MST for constant diameter graphs
• Fast distributed algorithms for girth, cycles and small subgraphs

This page was built for publication: The distributed minimum spanning tree problem

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