TY - GEN
T1 - Parallel algorithm for cograph recognition with applications
AU - He, Xin
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log2n) time with O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain a parallel algorithm for the permutation representation problem for cographs using O(log n) time with O(n) processors. We also present a parallel algorithm for the depthfirst spanning tree problem for permutation graphs (a class properly contains cographs) which takes O(log2n) time with O(n) processors.
AB - We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log2n) time with O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain a parallel algorithm for the permutation representation problem for cographs using O(log n) time with O(n) processors. We also present a parallel algorithm for the depthfirst spanning tree problem for permutation graphs (a class properly contains cographs) which takes O(log2n) time with O(n) processors.
UR - https://www.scopus.com/pages/publications/85029658474
U2 - 10.1007/3-540-55706-7_9
DO - 10.1007/3-540-55706-7_9
M3 - Conference contribution
AN - SCOPUS:85029658474
SN - 9783540557067
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 94
EP - 105
BT - Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings
A2 - Nurmi, Otto
A2 - Ukkonen, Esko
PB - Springer Verlag
T2 - 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992
Y2 - 8 July 1992 through 10 July 1992
ER -