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 language | English |
|---|---|
| Pages (from-to) | 341-344 |
| Number of pages | 4 |
| Journal | Applied Mathematics Letters |
| Volume | 20 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2007 Mar 1 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Applied Mathematics
Cite this
}
A faster parallel connectivity algorithm on cographs. / Hsieh, Sun-Yuan.
In: Applied Mathematics Letters, Vol. 20, No. 3, 01.03.2007, p. 341-344.Research output: Contribution to journal › Article
TY - JOUR
T1 - A faster parallel connectivity algorithm on cographs
AU - Hsieh, Sun-Yuan
PY - 2007/3/1
Y1 - 2007/3/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33751192472&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33751192472&partnerID=8YFLogxK
U2 - 10.1016/j.aml.2006.05.003
DO - 10.1016/j.aml.2006.05.003
M3 - Article
AN - SCOPUS:33751192472
VL - 20
SP - 341
EP - 344
JO - Applied Mathematics Letters
JF - Applied Mathematics Letters
SN - 0893-9659
IS - 3
ER -