A faster parallel connectivity algorithm on cographs

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

Cographs are a well-known class of graphs arising in a wide spectrum of practical applications. In this note, we show that the connected components of a cograph G can be optimally found in O (log log log Δ (G)) time using O (frac((n + m), log log log Δ (G))) processors on a common CRCW PRAM, or in O (log Δ (G)) time using O (frac((n + m), log Δ (G))) processors on an EREW PRAM, where Δ (G) is the maximum degree of G, and n and m respectively are the numbers of vertices and edges of G. These are faster than the previously best known result on general graphs.

Original languageEnglish
Pages (from-to)341-344
Number of pages4
JournalApplied Mathematics Letters
Volume20
Issue number3
DOIs
Publication statusPublished - 2007 Mar

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A faster parallel connectivity algorithm on cographs'. Together they form a unique fingerprint.

Cite this