Approximate minimum directed spanning trees under congestion

DOI10.1007/978-3-030-79527-6_20OpenAlexW3175255709MaRDI QIDQ2117742

Hossein Vahidi, Christoph Lenzen

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-79527-6_20

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Algebraic methods in the congested clique
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Toward Optimal Bounds in the Congested Clique
• On the power of the congested clique model
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Powers of tensors and fast matrix multiplication
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Distributed Verification and Hardness of Distributed Approximation
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• 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