TY - JOUR

T1 - On parallel recognition of cographs

AU - Hsieh, Sun Yuan

N1 - Funding Information:
The work was supported in part by the National Science Council under grants NSC92-2213-E-006-054 and NSC93-2213-E-006-021. Tel.: +886 6 2757575. E-mail address: hsiehsy@mail.ncku.edu.tw.

PY - 2011/3/4

Y1 - 2011/3/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79151471976&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79151471976&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.11.003

DO - 10.1016/j.tcs.2010.11.003

M3 - Article

AN - SCOPUS:79151471976

VL - 412

SP - 686

EP - 694

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 8-10

ER -