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

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

doi:10.1145/237502.237563

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

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

Research output: Contribution to conference › Paper › peer-review

43 Scopus citations

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)
Pages	243-250
Number of pages	8
DOIs	https://doi.org/10.1145/237502.237563
State	Published - 1996
Externally published	Yes
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

All Science Journal Classification (ASJC) codes

Software
Safety, Risk, Reliability and Quality

Access to Document

10.1145/237502.237563

Cite this

@conference{4a03cda0264448249e1bbae10dfb1744,

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

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures ; Conference date: 24-06-1996 Through 26-06-1996",

year = "1996",

doi = "10.1145/237502.237563",

language = "English (US)",

pages = "243--250",

}

TY - CONF

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 - https://www.scopus.com/pages/publications/0030387155

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

U2 - 10.1145/237502.237563

DO - 10.1145/237502.237563

M3 - Paper

AN - SCOPUS:0030387155

SP - 243

EP - 250

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

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this