Approximating the minimum spanning tree weight in sublinear time

Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations


We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of maximum degree d, with edge weights in the set 1... wg, and given a parameter 0 < ε < 1/2, estimates in time O(dwε-2 log w) the weight of the minimum spanning tree of G with a relative error of at most. Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of (dwε-2) on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time O(d-2 log-1) the number of connected components of an unweighted graph to within an additive error of εn. The time bound is shown to be tight up to within the log-1 factor. Our connectedcomponents algorithm picks O(1/ε2) vertices in the graph and then grows local spanning trees whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
EditorsFernando Orejas, Paul G. Spirakis, Jan van Leeuwen
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540422870, 9783540422877
StatePublished - 2001
Event28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete, Greece
Duration: Jul 8 2001Jul 12 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2076 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other28th International Colloquium on Automata, Languages and Programming, ICALP 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximating the minimum spanning tree weight in sublinear time'. Together they form a unique fingerprint.

Cite this