Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-14 Summary

A Simple Optimal Parallel List Ranking Algorithm, May 1987 Karl Abrahamson, Norm Dadoun, David G. Kirkpatrick and Teresa Maria Przytycka

We describe a randomized parallel algorithm to solve list ranking in $O(\log n)$ expected time using $n/ \log n$ processors, where $n$ is the length of the list. The algorithm requires considerably less load rebalancing than previous algorithms.

If you have any questions or comments regarding this page please send mail to