We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A PARALLEL ALGORITHM FOR FOREST RECONSTRUCTION.
- Authors
OLARIU, STEPHAN; WEN, ZHAOFANG
- Abstract
The purpose of this short note is to show that the problem of reconstructing a directed forest from a collection of leaf-to-root paths can be done efficiently in parallel by reducing the problem to integer sorting. Specifically, given M the total length of the paths in the collection, and n the number of distinct node labels, our algorithm reconstructs the corresponding forest (if such a forest exists) in O(M/p) time using p ≤ M/n processors or time using M/n < p < M processors, and (M) space on the EREW-PRAM.
- Publication
Parallel Processing Letters, 1992, Vol 2, Issue 2/3, p157
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626492000271