An optimal linked list prefix algorithms on a local memory computer
Yijie Han · 1989
We present a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefix 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. We also show that a maximal matching for a linked list can be computed in O(logG(n)) time with n processors and n shared cells.