On the public citation graph

Estimating the weight of metric minimum spanning trees in sublinear-time

0 signed · 44 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-45253-2_15openalex-snapshot
Property Testing in Computational Geometry
inferredcites →https://doi.org/10.1007/3-540-48224-5_16openalex-snapshot
Approximating the Minimum Spanning Tree Weight in Sublinear Time
inferredcites →https://doi.org/10.1007/978-3-662-21711-5_16openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1007/springerreference_57547openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1016/b978-044482537-7/50010-3openalex-snapshot
Spanning Trees and Spanners
inferredcites →https://doi.org/10.1109/sfcs.1996.548459openalex-snapshot
The regularity lemma and approximation schemes for dense problems
inferredcites →https://doi.org/10.1109/sfcs.1998.743487openalex-snapshot
Fast Monte-Carlo algorithms for finding low-rank approximations
inferredcites →https://doi.org/10.1109/sfcs.2000.892111openalex-snapshot
Testing of clustering
inferredcites →https://doi.org/10.1109/sfcs.2003.1238173openalex-snapshot
Proceedings 44th IEEE Symposium on Foundations of Computer Science - FOCS 2003
inferredcites →https://doi.org/10.1109/sffcs.1999.814587openalex-snapshot
A sublinear time approximation scheme for clustering in metric spaces
inferredcites →https://doi.org/10.1137/0211059openalex-snapshot
On Constructing Minimum Spanning Trees in k -Dimensional Spaces and Related Problems
inferredcites →https://doi.org/10.1137/1.9780898714906openalex-snapshot
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
inferredcites →https://doi.org/10.1137/1.9780898715583openalex-snapshot
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
inferredcites →https://doi.org/10.1137/s0097539702403244openalex-snapshot
Approximating the Minimum Spanning Tree Weight in Sublinear Time
inferredcites →https://doi.org/10.1145/200836.200853openalex-snapshot
A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
inferredcites →https://doi.org/10.1145/201019.201022openalex-snapshot
A randomized linear-time algorithm to find minimum spanning trees
inferredcites →https://doi.org/10.1145/285055.285060openalex-snapshot
Property testing and its connection to learning and approximation
inferredcites →https://doi.org/10.1145/301250.301366openalex-snapshot
Sublinear time algorithms for metric space problems
inferredcites →https://doi.org/10.1145/355541.355562openalex-snapshot
A minimum spanning tree algorithm with inverse-Ackermann type complexity
inferredcites →https://doi.org/10.1145/505241.505243openalex-snapshot
An optimal minimum spanning tree algorithm
inferredcites →https://doi.org/10.1145/780542.780590openalex-snapshot
A sublinear algorithm for weakly approximating edit distance
inferredcites →https://doi.org/10.1145/780542.780620openalex-snapshot
Sublinear geometric algorithms
inferredcites →https://doi.org/10.5555/365411.365499openalex-snapshot
Sublinear time approximate clustering
inferredcites →https://doi.org/10.5555/644108.644242openalex-snapshot
Sublinear-time approximation of Euclidean minimum spanning tree

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11523468_70openalex-snapshot
Facility Location in Sublinear Time
inferred← citeshttps://doi.org/10.1007/978-3-032-27732-9_37openalex-snapshot
Minimizing Makespan in Sublinear Time via Weighted Random Sampling
inferred← citeshttps://doi.org/10.1007/978-3-540-85097-7_8openalex-snapshot
Separating Sublinear Time Computations by Approximate Diameter
inferred← citeshttps://doi.org/10.1007/978-3-642-29700-7_16openalex-snapshot
A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing
inferred← citeshttps://doi.org/10.1007/s00186-025-00898-zopenalex-snapshot
Sublinear time approximation schemes for makespan minimization on parallel machines
inferred← citeshttps://doi.org/10.1007/s10878-009-9248-3openalex-snapshot
Separating sublinear time computations by approximate diameter
inferred← citeshttps://doi.org/10.1016/j.cosrev.2008.10.002openalex-snapshot
The saga of minimum spanning trees
inferred← citeshttps://doi.org/10.1016/j.ipl.2014.05.008openalex-snapshot
Estimating the number of connected components in sublinear time
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.04.040openalex-snapshot
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.08.006openalex-snapshot
A sublinear-time approximation scheme for bin packing
inferred← citeshttps://doi.org/10.1109/focs.2008.81openalex-snapshot
Constant-Time Approximation Algorithms via Local Improvements
inferred← citeshttps://doi.org/10.1109/icde65706.2026.00012openalex-snapshot
Approximate Butterfly Counting in Sublinear Time
inferred← citeshttps://doi.org/10.1145/1007352.1007413openalex-snapshot
Algorithms for dynamic geometric problems over data streams
inferred← citeshttps://doi.org/10.1145/1064092.1064116openalex-snapshot
Sampling in dynamic data streams and applications
inferred← citeshttps://doi.org/10.1145/1137856.1137912openalex-snapshot
Online geometric reconstruction
inferred← citeshttps://doi.org/10.1145/1367064.1367071openalex-snapshot
Testing Euclidean minimum spanning trees in the plane
inferred← citeshttps://doi.org/10.1145/1989727.1989728openalex-snapshot
Online geometric reconstruction
inferred← citeshttps://doi.org/10.1145/3502733openalex-snapshot
Constant Time Graph Neural Networks
inferred← citeshttps://doi.org/10.1145/3564246.3585168openalex-snapshot
Streaming Euclidean MST to a Constant Factor
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2019.6openalex-snapshot
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.