Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
From MaRDI portal
Publication:3580979
DOI10.1145/1007352.1007407zbMath1192.68319MaRDI QIDQ3580979
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W15: Distributed algorithms
Related Items
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, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms