Approximate minimum directed spanning trees under congestion

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

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

• Powers of tensors and fast matrix multiplication
• Distributed Verification and Hardness of Distributed Approximation
• Optimum branchings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Title not available (Why is that?)
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On the power of the congested clique model
• Algebraic methods in the congested clique
• Toward optimal bounds in the congested clique, graph connectivity and MST
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Title not available (Why is that?)
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• MST in Log-Star Rounds of Congested Clique
• Single-Source Shortest Paths in the CONGEST Model with Improved Bound

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)