Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time

DOI10.1137/060672121MaRDI QIDQ3575153zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

randomized algorithmsapproximation algorithmssublinear-time algorithms

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 2079416 (Why is no real title available?)
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• 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)