A short overview is given over the various computer models: parallel (PRAM and distributed-memory), and external. Then the list-ranking problem is introduced and motivated. An elementary algorithm, pointer-jumping, has poor performance. Therefore, we look further. A general and new approach for solving the list-ranking problem is presented. It is tuned towards parallel computers. This algorithm, achieves speed-up on an Intel Paragon with 100 processors. A slight modification of the algorithm is suited as an external-memory algorithm. It is several times faster than the best algorithm that existed before.
The talk is intended to be understandable to anyone: many pictures, minimal notation and technical terms. Some members of AG1 may already know the essentials of this talk. For those who want to know the background: the talk is based on TR 97-1021.