Parallel recognition of complement reducible graphs and cotree construction

AbstractA simple parallel algorithm is presented for constructing parse tree representation of a rich family of graphs known as cographs. From the parse tree representation of a cograph it is possible to compute efficiently many properties which are difficult to compute for general graphs. The construction algorithm runs in O(log2n) parallel time using O(n3/log2n) processors on a CREW PRAM