Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
From MaRDI portal
Publication:3575153
DOI10.1137/060672121zbMATH Open1192.68855OpenAlexW2001342485MaRDI QIDQ3575153FDOQ3575153
Authors: 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
Recommendations
- Estimating the weight of metric minimum spanning trees in sublinear-time
- scientific article; zbMATH DE number 1756011
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
- scientific article; zbMATH DE number 2079416
- Minimum-weight spanning tree algorithms. A survey and empirical study
- Minimum spanning trees for tree metrics: Abridgements and adjustments
- On the weight-constrained minimum spanning tree problem
Cited In (19)
- Sublinear time algorithms for metric space problems
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Sublinear-time Algorithms
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Approximately counting triangles in sublinear time
- Dynamic graph stream algorithms in \(o(n)\) space
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- Title not available (Why is that?)
- Title not available (Why is that?)
- On random perfect matchings in metric spaces with not-too-large diameters
- Sublinear time estimation of degree distribution moments: the arboricity connection
- Constant-time dynamic weight approximation for minimum spanning forest
- 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
- Sublinear algorithms for \((1.5+\epsilon)\)-approximate matching
- On approximating the number of \(k\)-cliques in sublinear time
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 Q3575153)
