A distributed algorithm for directed minimum-weight spanning tree

DOI10.1007/s00446-021-00398-3OpenAlexW3173612603MaRDI QIDQ2689838

Rotem Oshman, Orr Fischer

Publication date: 14 March 2023

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-021-00398-3

zbMATH Keywords

distributed computingarborescencedirected minimum spanning treeCONGEST

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster distributed protocol for constructing a minimum spanning tree
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• On the distributional complexity of disjointness
• Algebraic methods in the congested clique
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Deterministic coin tossing with applications to optimal parallel list ranking
• A note on finding optimum branchings
• Thek best spanning arborescences of a network
• The Probabilistic Communication Complexity of Set Intersection
• Finding optimum branchings
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
• Distributed Verification and Hardness of Distributed Approximation
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
• A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Improved distributed algorithms for exact shortest paths
• Distributed approximation algorithms for weighted shortest paths
• Sub-linear distributed algorithms for sparse certificates and biconnected components
• MST in Log-Star Rounds of Congested Clique
• Optimum branchings
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Single-Source Shortest Paths in the CONGEST Model with Improved Bound