### 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

## 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)