Approximating the Minimum Spanning Tree Weight in Sublinear Time

DOI10.1137/S0097539702403244zbMATH Open1081.68120MaRDI QIDQ5317201FDOQ5317201

Authors: Ronitt Rubinfeld, Luca Trevisan, Bernard Chazelle 

Publication date: 16 September 2005

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

Recommendations

• scientific article; zbMATH DE number 1756011
• Estimating the number of connected components in sublinear time
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• A fast distributed approximation algorithm for minimum spanning trees

zbMATH Keywords

minimum spanning treerandomized algorithmsapproximation algorithmssublinear time algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cited In (41)

• Approximating minimum-cost graph problems with spanning tree edges
• On the probe complexity of local computation algorithms
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs
• Sublinear-time Algorithms
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Separating sublinear time computations by approximate diameter
• Unique entity estimation with application to the Syrian conflict
• Approximately counting triangles in sublinear time
• Dynamic graph stream algorithms in \(o(n)\) space
• Separating Sublinear Time Computations by Approximate Diameter
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Quantum Chebyshev's Inequality and Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimum-weight spanning tree algorithms. A survey and empirical study
• The saga of minimum spanning trees
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Testing connectedness of images
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Seeding with costly network information
• Sublinear time estimation of degree distribution moments: the arboricity connection
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Constant-time dynamic weight approximation for minimum spanning forest
• A note on the traveling salesman reoptimization problem under vertex insertion
• Estimating the number of connected components in sublinear time
• Title not available (Why is that?)
• Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph
• Can we locally compute sparse connected subgraphs?
• Sublinear graph approximation algorithms
• Testing outerplanarity of bounded degree graphs
• Streaming Euclidean MST to a constant factor
• On approximating the number of \(k\)-cliques in sublinear time
• Local algorithms for sparse spanning graphs
• Estimating the number of connected components in a graph via subgraph sampling
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Constructing near spanning trees with few local inspections

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

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