Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-30 Summary

A Parallel Tree Contraction Algorithm, August 1987 Karl Abrahamson, Norm Dadoun, David G. Kirkpatrick and Teresa Maria Przytycka

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.

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