Approximating the Minimum Spanning Tree Weight in Sublinear Time
From MaRDI portal
Publication:5317201
DOI10.1137/S0097539702403244zbMath1081.68120MaRDI QIDQ5317201
Luca Trevisan, Ronitt Rubinfeld, Bernard Chazelle
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Sublinear-time Algorithms, Sublinear Graph Approximation Algorithms, Separating Sublinear Time Computations by Approximate Diameter, Separating sublinear time computations by approximate diameter, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Estimating the number of connected components in sublinear time