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 -