EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS

Journal article

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. © 1994.

Authors: Gibbons, J; Cai, W; Skillicorn, D

• Publication status: Published
• Journal: SCIENCE OF COMPUTER PROGRAMMING
• Volume: 23
• Issue: 1
• Pages: 1-18
• Publication date: 1994-10-01
• DOI: 10.1016/0167-6423(94)00013-1
• ISSN: 0167-6423
• Language: English