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 G can be optimally found in O (log log log Delta (G)) time using O ((n+m)/log log log Delta(G)) processors on a common CRCW PRAM, or in O (log Delta (G)) time using O ((n+m)/ log Delta (G)) processors on an EREW PRAM, where Delta(G) is the maximum degree of G, and n and m respectively are the numbers of vertices and edges of G. These are faster than the previously best known result on general graphs. (c) 2006 Elsevier Ltd. All rights reserved.