Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time

DOI10.1137/060672121zbMath1192.68855OpenAlexW2001342485MaRDI QIDQ3575153

Christian Sohler, Artur Czumaj

Publication date: 7 July 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/2416/1/WRAP_Czumaj_estimating_weight.pdf

zbMATH Keywords

approximation algorithmsrandomized algorithmssublinear-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (10)

On random perfect matchings in metric spaces with not-too-large diameters ⋮ Can we locally compute sparse connected subgraphs? ⋮ Approximately Counting Triangles in Sublinear Time ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Testing Euclidean Spanners ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Sublinear-time Algorithms ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Unnamed Item

This page was built for publication: Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time