Parallel Recognition of Complement Reducible Graphs and Cotree Construction

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.