A deterministic algorithm computes a (1+ε)-approximate MST in doubling metrics in time 2^{O(ddim)} n(log n + ε^{-1} log^4(1/ε)), improving prior ε^{-O(ddim)} dependence.
Sublinear-time algorithm for mst-weight revisited
1 Pith paper cite this work, alongside 1 external citations. Polarity classification is still indexing.
1
Pith paper citing it
1
external citations · OpenAlex
fields
cs.DS 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Fast and Simple $(1+\epsilon)$-Approximation for Minimum Spanning Trees in Doubling Metrics
A deterministic algorithm computes a (1+ε)-approximate MST in doubling metrics in time 2^{O(ddim)} n(log n + ε^{-1} log^4(1/ε)), improving prior ε^{-O(ddim)} dependence.