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

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

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 proceeding › Conference 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 2^{log* 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 language	English (US)
Title of host publication	Annual ACM Symposium on Parallel Algorithms and Architectures
Editors	Anon
Pages	243-250
Number of pages	8
State	Published - 1996
Event	Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures - Padua, Italy Duration: Jun 24 1996 → Jun 26 1996

Other

Other	Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures
City	Padua, Italy
Period	6/24/96 → 6/26/96

ASJC Scopus subject areas

Software
Safety, Risk, Reliability and Quality

Cite this

@inproceedings{5a1e955e7caf404d9509bbbaa1553799,

title = "Finding minimum spanning forests in logarithmic time and linear work using random sampling",

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.",

author = "Richard Cole and Klein, {Philip N.} and Tarjan, {Robert E.}",

year = "1996",

language = "English (US)",

pages = "243--250",

editor = "Anon",

booktitle = "Annual ACM Symposium on Parallel Algorithms and Architectures",

note = "Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures ; Conference date: 24-06-1996 Through 26-06-1996",

}

TY - GEN

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

AU - Cole, Richard

AU - Klein, Philip N.

AU - Tarjan, Robert E.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030387155&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030387155&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0030387155

SP - 243

EP - 250

BT - Annual ACM Symposium on Parallel Algorithms and Architectures

A2 - Anon, null

T2 - Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures

Y2 - 24 June 1996 through 26 June 1996

ER -

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

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this