### 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

}

*Applied Mathematics Letters*, vol. 20, no. 3, pp. 341-344. https://doi.org/10.1016/j.aml.2006.05.003

**A faster parallel connectivity algorithm on cographs.** / Hsieh, Sun-Yuan.

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 -