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

DOI10.1137/S0097539703435297zbMATH Open1086.68144MaRDI QIDQ5700570FDOQ5700570

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

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

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

Recommendations

• scientific article; zbMATH DE number 1756011
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• scientific article; zbMATH DE number 2079416
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Estimating the weight of metric minimum spanning trees in sublinear-time
• A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

Cited in

(23)

• scientific article; zbMATH DE number 2079416 (Why is no real title available?)
• Testing Euclidean Spanners
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Sublinear-time Algorithms
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Can we locally compute sparse connected subgraphs?
• Approximately counting triangles in sublinear time
• Separating Sublinear Time Computations by Approximate Diameter
• Streaming Euclidean MST to a constant factor
• On approximating the number of \(k\)-cliques in sublinear time
• Approximate geometric MST range queries
• Lower bounds for testing Euclidean minimum spanning trees
• Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph
• A sublinear-time approximation scheme for bin packing
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Separating sublinear time computations by approximate diameter
• Conic nearest neighbor queries and approximate Voronoi diagrams
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
• SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
• Dynamic graph stream algorithms in \(o(n)\) space

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

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