Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
From MaRDI portal
Publication:5700570
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)
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
- Time-space trade-offs for computing Euclidean minimum spanning trees
- Time-space trade-offs for computing 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 (22)
- Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
- Sublinear-time Algorithms
- Lower bounds for testing Euclidean minimum spanning trees
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
- Separating sublinear time computations by approximate diameter
- Dynamic graph stream algorithms in \(o(n)\) space
- Separating Sublinear Time Computations by Approximate Diameter
- Time-space trade-offs for computing Euclidean minimum spanning trees
- On Approximating the Number of $k$-Cliques in Sublinear Time
- Title not available (Why is that?)
- A sublinear-time approximation scheme for bin packing
- Conic nearest neighbor queries and approximate Voronoi diagrams
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
- Testing Euclidean Spanners
- Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph
- Can we locally compute sparse connected subgraphs?
- Streaming Euclidean MST to a constant factor
- Approximately Counting Triangles in Sublinear Time
- Title not available (Why is that?)
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)
