Approximate minimum directed spanning trees under congestion

DOI10.1007/978-3-030-79527-6_20MaRDI QIDQ2117742zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Hossein Vahidi

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

• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• scientific article; zbMATH DE number 3373559 (Why is no real title available?)
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Distributed verification and hardness of distributed approximation
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• MST in \(O(1)\) rounds of congested clique
• MST in log-star rounds of congested clique
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• On the power of the congested clique model
• Optimum branchings
• Powers of tensors and fast matrix multiplication
• Single-Source Shortest Paths in the CONGEST Model with Improved Bound
• The distributed minimum spanning tree problem
• Toward optimal bounds in the congested clique, graph connectivity and MST

Cited in

(1)

• Hardness results and an exact exponential algorithm for the spanning tree congestion problem

This page was built for publication: Approximate minimum directed spanning trees under congestion

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