
The Library
Estimating the weight of metric minimum spanning trees in sublinear time
Tools
Czumaj, Artur and Sohler, Christian (2009) Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, Vol.39 (No.3). pp. 904-922. doi:10.1137/060672121 ISSN 0097-5397.
![]()
|
PDF
WRAP_Czumaj_estimating_weight.pdf - Requires a PDF viewer. Download (275Kb) |
Official URL: http://dx.doi.org/10.1137/060672121
Abstract
In this paper we present a sublinear-time $(1+\varepsilon)$-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an $n$-point metric space. The running time of the algorithm is $\widetilde{\mathcal{O}}(n/\varepsilon^{\mathcal{O}(1)})$. Since the full description of an $n$-point metric space is of size $\Theta(n^2)$, the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in $o(n)$ time the weight of the minimum spanning tree to within any factor. We also show that no deterministic algorithm can achieve a $B$-approximation in $o(n^2/B^3)$ time. Furthermore, it has been previously shown that no $o(n^2)$ algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Spanning trees (Graph theory), Estimation theory -- Computer programs, Algorithms | ||||
Journal or Publication Title: | SIAM Journal on Computing | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 26 August 2009 | ||||
Dates: |
|
||||
Volume: | Vol.39 | ||||
Number: | No.3 | ||||
Page Range: | pp. 904-922 | ||||
DOI: | 10.1137/060672121 | ||||
Status: | Peer Reviewed | ||||
Access rights to Published version: | Open Access (Creative Commons) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year