On parallel recognition of cographs

Research output: Contribution to journalArticlepeer-review

Abstract

In 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 (13) (2005) 182215] 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: 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.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.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.

Original languageEnglish
Pages (from-to)686-694
Number of pages9
JournalTheoretical Computer Science
Volume412
Issue number8-10
DOIs
Publication statusPublished - 2011 Mar 4

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On parallel recognition of cographs'. Together they form a unique fingerprint.

Cite this