Approximating the Minimum Spanning Tree Weight in Sublinear Time
From MaRDI portal
(Redirected from 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
(47)- Constructing near spanning trees with few local inspections
- Approximating minimum-cost graph problems with spanning tree edges
- Sublinear time approximation schemes for makespan minimization on parallel machines
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- On the probe complexity of local computation algorithms
- 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
- Streaming algorithms for geometric Steiner forest
- 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
- Erasure-resilient sublinear-time graph algorithms
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- Quantum Chebyshev's Inequality and Applications
- scientific article; zbMATH DE number 1756011 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- 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
- Sublinear algorithms and lower bounds for metric TSP cost estimation
- Graph coloring via degeneracy in streaming and other space-conscious models
- 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
- Simple sublinear algorithms for (+1) vertex coloring via asymmetric palette sparsification
- 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
- scientific article; zbMATH DE number 3974972 (Why is no real title available?)
- Sublinear time approximation of the cost of a metric k-nearest neighbor graph
- Can we locally compute sparse connected subgraphs?
- Testing outerplanarity of bounded degree graphs
- Sublinear graph approximation algorithms
- 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
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)
