On parallel recognition of cographs

AbstractIn this paper, we modify a known parallel cograph-recognition algorithm proposed by Nikolopoulos and Palios [S.D. Nikolopoulos, L. Palios, Efficient parallel recognition of cographs, Discrete Applied Mathematics 150 (1–3) (2005) 182–215] and provide a new analysis of the algorithm. Given an input graph G with n vertices and m edges, we obtain the following three results based on our analysis: 1.When G is k-regular for a fixed positive integer k, the cograph-recognition problem can be optimally solved in O(logn) time using O(n+mlogn) processors on an EREW PRAM.2.When G is k-regular for k=O(loglogn), the cograph-recognition problem can be solved in O(lognloglogn) time using O(n+mlogn) processors on an EREW PRAM.3.Given a positive integer α=O(loglogn), the cograph-recognition problem can be solved in O(lognloglogn) time using O(n+mlogn) processors on an EREW PRAM, provided the number of vertices in G with degree larger than α is at most O(logn). The above results improve upon the previously best known result, which took O(log2n) time using O(n+mlogn) processors on an EREW PRAM