Estimating the weight of metric minimum spanning trees in sublinear-time

DOI10.1145/1007352.1007386zbMath1192.68888OpenAlexW2061598457MaRDI QIDQ3580967

Christian Sohler, Artur Czumaj

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: http://wrap.warwick.ac.uk/2416/1/WRAP_Czumaj_estimating_weight.pdf

Mathematics Subject Classification ID

Trees (05C05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (7)

Separating sublinear time computations by approximate diameter ⋮ The saga of minimum spanning trees ⋮ Estimating the number of connected components in sublinear time ⋮ Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ A sublinear-time approximation scheme for bin packing ⋮ Separating Sublinear Time Computations by Approximate Diameter

This page was built for publication: Estimating the weight of metric minimum spanning trees in sublinear-time