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

DOI10.1145/1007352.1007386MaRDI QIDQ3580967zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• scientific article; zbMATH DE number 1756011
• scientific article; zbMATH DE number 1670813
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

Cited in

(14)

• scientific article; zbMATH DE number 2079416 (Why is no real title available?)
• Estimating the number of connected components in sublinear time
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• Sublinear time algorithms for metric space problems
• Separating Sublinear Time Computations by Approximate Diameter
• Streaming Euclidean MST to a constant factor
• A sublinear-time approximation scheme for bin packing
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Separating sublinear time computations by approximate diameter
• The saga of minimum spanning trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580967)