A faster parallel connectivity algorithm on cographs

DOI10.1016/J.AML.2006.05.003MaRDI QIDQ2371145zbMATH OpenOpenAlexFDO

Authors Sun-Yuan Hsieh

Publication date 29 June 2007

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2006.05.003

zbMATH Keywords

cographs connectivity parallel algorithms

Mathematics Subject Classification ID

Connectivity (05C40) Parallel algorithms in computer science (68W10)

Review text

In this note, it is shown that the connected components of a cograph \(G\) can be optimally found in \(O(\log\log\log\Delta(G))\) time using \(O(\frac{n+m}{\log\log\log\Delta(G)})\) processors on a common CRCW PRAM, or in \(O(\log\Delta(G))\) time using \(O(\frac{n+m}{\log\Delta(G)})\) processors on an EREW PRAM, where \(n=| V(G)| \) and \(m=| E(G)| \). For further reference, see \textit{O. Berkman, Y. Matias} and \textit{P. Radge} [J. Algorithms 28, No.~2, 197--215 (1998; Zbl 0919.68072)].

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A faster parallel connectivity algorithm on cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2371145)