A faster parallel connectivity algorithm on cographs

Cographs are a well-known class of graphs arising in a wide spectrum of practical applications. In this note, we show that the connected components of a cograph GG can be optimally found in O(logloglogΔ(G)) time using O((n+m)logloglogΔ(G)) processors on a common CRCW PRAM, or in O(logΔ(G)) time using O((n+m)logΔ(G)) processors on an EREW PRAM, where Δ(G) is the maximum degree of GG, and nn and mm respectively are the numbers of vertices and edges of GG. These are faster than the previously best known result on general graphs.