Parallel Algorithm for Cograph Recognition with Applications

We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log²n) time with O(n + m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain parallel algorithms for solving the maximum matching and the permutation representation problems for cographs using O(log n) time with O(n) processors. We also obtain a parallel algorithm for the depth-first spanning tree problem for permutation graphs (a class properly contains cographs) which takes O(log²n) time with O(n) processors.