A faster parallel connectivity algorithm on cographs

Research output: Contribution to journalArticle

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 1

Fingerprint

Cographs
Parallel algorithms
Connectivity
EREW PRAM
Graph in graph theory
Maximum Degree
Connected Components
Class

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Cite this

@article{b9d8b011bb62493fb6ded8200b67c3ea,
title = "A faster parallel connectivity algorithm on cographs",
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.",
author = "Sun-Yuan Hsieh",
year = "2007",
month = "3",
day = "1",
doi = "10.1016/j.aml.2006.05.003",
language = "English",
volume = "20",
pages = "341--344",
journal = "Applied Mathematics Letters",
issn = "0893-9659",
publisher = "Elsevier Limited",
number = "3",

}

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 journalArticle

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 -