Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

DOI10.1137/S0097539703435297zbMath1086.68144MaRDI QIDQ5700570

Christian Sohler, Ilan Newman, Ronitt Rubinfeld, Avner Magen, Funda Ergün, Lance J. Fortnow, Artur Czumaj

Publication date: 28 October 2005

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

zbMATH Keywords

minimum spanning treesublinear algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (14)

Separating sublinear time computations by approximate diameter ⋮ Can we locally compute sparse connected subgraphs? ⋮ Approximately Counting Triangles in Sublinear Time ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS ⋮ Testing Euclidean Spanners ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Conic nearest neighbor queries and approximate Voronoi diagrams ⋮ Sublinear-time Algorithms ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ 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 ⋮ Unnamed Item

This page was built for publication: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time