Czumaj, Artur and Sohler, C.. (2009) Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM Journal on Computing (SICOMP), 39 (3). pp. 904-922. ISSN 0097-5397

Full text not available from this repository.

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
Journal or Publication Title:	SIAM Journal on Computing (SICOMP)
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0097-5397
Date:	2009
Volume:	39
Number:	3
Page Range:	pp. 904-922
Identification Number:	10.1137/060672121
Publication Status:	Published
Related URLs:	Other Repository
URI:	http://wrap.warwick.ac.uk/id/eprint/47508

Request changes to a record

Actions (login required)

View Item