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)
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (26)
Unique entity estimation with application to the Syrian conflict ⋮ Separating sublinear time computations by approximate diameter ⋮ Can we locally compute sparse connected subgraphs? ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Seeding with Costly Network Information ⋮ Unnamed Item ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Constructing near spanning trees with few local inspections ⋮ The saga of minimum spanning trees ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ Testing outerplanarity of bounded degree graphs ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Estimating the number of connected components in sublinear time ⋮ Sublinear-time Algorithms ⋮ Sublinear Graph Approximation Algorithms ⋮ Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms ⋮ Local algorithms for sparse spanning graphs ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Separating Sublinear Time Computations by Approximate Diameter ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Approximating the Minimum Spanning Tree Weight in Sublinear Time
