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

DOI10.1145/1007352.1007407zbMath1192.68319MaRDI 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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W15: Distributed algorithms

Related Items

Distributed Graph Algorithms and their Complexity: An Introduction, Unnamed Item, Distributed MST for constant diameter graphs, Local MST computation with short advice, Fast deterministic distributed algorithms for sparse spanners, A fast distributed approximation algorithm for minimum spanning trees, Redundancy in distributed proofs, Low-congestion shortcut and graph parameters, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Low-congestion shortcuts without embedding