List ranking

In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As harvtxt|Anderson|Miller|1990 write, 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 harvtxt|Wyllie|1979, who solved it with a parallel algorithm using logarithmic time and O("n" log "n") steps. Over a sequence of many subsequent papers, this was eventually improved to linearly many steps, on the most restrictive model of synchronous shared-memory parallel computation, the exclusive read exclusive write PRAM (harvnb|Cole|Vishkin|1989; harvnb|Anderson|Miller|1990).

List ranking can equivalently be viewed as performing a prefix sum operation on the given list, in which the values to be summed are all equal to one. 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 harv|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.

References

*citation
last1 = Anderson | first1 = Richard J.
last2 = Miller | first2 = Gary L.
title = A simple randomized parallel algorithm for list-ranking
journal = Information Processing Letters
volume = 33 | issue = 5 | year = 1990 | doi = 10.1016/0020-0190(90)90196-5 | pages = 269–273.

*citation
last1 = Cole | first1 = Richard
last2 = Vishkin | first2 = Uzi
title = Faster optimal parallel prefix sums and list ranking
journal = Information and Computation
volume = 81 | issue = 3 | year = 1989 | pages = 334–352 | doi = 10.1016/0890-5401(89)90036-9.

*citation
last1 = Tarjan | first1 = Robert E. | authorlink1 = Robert E. Tarjan
last2 = Vishkin | first2 = Uzi
title = An efficient parallel biconnectivity algorithm
journal = SIAM Journal on Computing
volume = 14 | issue = 4 | year = 1985 | doi = 10.1137/0214061 | pages = 862–874.

*citation
last = Wyllie | first = J. C.
title = The Complexity of Parallel Computation
publisher = Ph.D. thesis, Department of Computer Science, Cornell University
year = 1979.