Technical Reports

The ICICS/CS Reading Room

UBC CS TR-88-01 Summary

Parallel Recognition of Complement Reducible Graphs and Cotree Construction, January 1988 David G. Kirkpatrick and Teresa Maria Przytycka

A simple parallel algorithm is presented for constructing parse tree representations of graphs in a rich family known as cographs. From the parse tree representation of a cograph it is possible to compute in an efficient way many properties which are difficult for general graphs. The presented algorithm runs in O$(\log^{2} n)$ parallel time using O$(n^{3} / \log^{2} n)$ processors on a CREW PRAM.

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