Efficient Parallel Algorithms for Tree Accumulations
Jeremy Gibbons‚ Wentong Cai and David Skillicorn
Abstract
Accumulations are higher-order operations on structured objects; they leave the shape of an object unchanged, but replace elements of that object with accumulated information about other elements. Upwards and downwards accumulations on trees are two such operations; they form the basis of many tree algorithms. We present two EREW PRAM algorithms for computing accumulations on trees taking O(\log n) time on O(n/\log n) processors, which is optimal.
Details
| Journal |
Science of Computer Programming |
| Pages |
1–18 |
| Volume |
23 |
| Year |
1994 |
Links
Related pages
|
People |
|
|
Activities |