A Simple Parallel Tree Contraction Algorithm

A simple reduction from the tree contraction problem to the list ranking problem is presented. The reduction takes O$(\log n)$ time for a tree with $n$ nodes, using O$(n / \log n)$ EREW processors. Thus tree contraction can be done as efficiently as list ranking. A broad class of parallel tree computations to which the tree contraction techniques apply is described. This subsumes earlier characterizations. Applications to the computation of certain properties of cographs are presented in some detail.