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

Preview

PDF WRAP_Czumaj_estimating_weight.pdf - Requires a PDF viewer. Download (275Kb)

Request Changes to record.

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 > 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:	Date Event 26 August 2009 Published
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

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