On parallel recognition of cographs

研究成果: Article同行評審

摘要

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.

原文English
頁(從 - 到)686-694
頁數9
期刊Theoretical Computer Science
412
發行號8-10
DOIs
出版狀態Published - 2011 三月 4

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

指紋 深入研究「On parallel recognition of cographs」主題。共同形成了獨特的指紋。

引用此