List ranking

As Anderson & Miller (1990) wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.

The list ranking problem was posed by Wyllie (1979), who solved it with a parallel algorithm using logarithmic time and O(n log n) total steps (that is, O(n) processors).

Over a sequence of many subsequent papers, this was eventually improved to linearly many steps (O(n/log n) processors), on the most restrictive model of synchronous shared-memory parallel computation, the exclusive read exclusive write PRAM (Vishkin 1984; Cole & Vishkin 1989;Anderson & Miller 1990).

The list ranking problem can be used to solve many problems on trees via an Euler tour technique, in which one forms a linked list that includes two copies of each edge of the tree, one in each direction, places the nodes of this list into an ordered array using list ranking, and then performs prefix sum computations on the ordered array (Tarjan & Vishkin 1985).

For instance, the height of each node in the tree may be computed by an algorithm of this type in which the prefix sum adds 1 for each downward edge and subtracts 1 for each upward edge.