Efficient Parallel Algorithms for Tree Accumulations
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...
| Váldodahkkit: | , , |
|---|---|
| Materiálatiipa: | Journal article |
| Almmustuhtton: |
1994
|
| Čoahkkáigeassu: | 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. |
|---|