Finding minimum spanning forests in logarithmic time and linear work using random sampling

Richard Cole, Philip N. Klein, Robert E. Tarjan

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

Abstract

We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2log* n off the best previous running time for a linear-work algorithm. The novelty in our approach is to divide the computation into two phases, the first of which finds only a partial solution. This idea has been used previously in parallel connected components algorithms.

Original languageEnglish (US)
Title of host publicationAnnual ACM Symposium on Parallel Algorithms and Architectures
Editors Anon
Pages243-250
Number of pages8
StatePublished - 1996
EventProceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures - Padua, Italy
Duration: Jun 24 1996Jun 26 1996

Other

OtherProceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures
CityPadua, Italy
Period6/24/966/26/96

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'Finding minimum spanning forests in logarithmic time and linear work using random sampling'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., Klein, P. N., & Tarjan, R. E. (1996). Finding minimum spanning forests in logarithmic time and linear work using random sampling. In Anon (Ed.), Annual ACM Symposium on Parallel Algorithms and Architectures (pp. 243-250)