Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem

DOI10.1145/1007352.1007407zbMath1192.68319OpenAlexW2172178473MaRDI QIDQ3580979

Michael Elkin

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007407

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (13)

Single-source shortest paths in the CONGEST model with improved bounds ⋮ Low-congestion shortcuts without embedding ⋮ Local MST computation with short advice ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ Low-congestion shortcut and graph parameters ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Distributed MST for constant diameter graphs ⋮ Unnamed Item

This page was built for publication: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem