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