An optimal linked list prefix algorithm on a local memory computer
Yijie Han · IEEE Transactions on Computers · 1991
The author presents a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefixs for an input list of n elements in time O(n/p+logn) on a local memory PRAM model using p processors and p shared memory cells.>