An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem

Related Items (20)

Latency, capacity, and distributed minimum spanning trees ⋮ Low-congestion shortcuts without embedding ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Minimum cost flow in the CONGEST model ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Low-congestion shortcut and graph parameters ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Unnamed Item ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Spanner Approximation ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Approximate minimum directed spanning trees under congestion

This page was built for publication: An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem