An asynchronous parallel algorithm for undirected graph connectivity

Richard Cole; Ofer Zajicek

doi:10.1006/jagm.1995.1002

An asynchronous parallel algorithm for undirected graph connectivity

Richard Cole, Ofer Zajicek

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

An algorithm for computing the components of an undirected graph in the (asynchronous) APRAM model is given; the algorithm uses O(n + e) processes and O(log n) rounds.

Original language	English (US)
Pages (from-to)	50-97
Number of pages	48
Journal	Journal of Algorithms
Volume	18
Issue number	1
DOIs	https://doi.org/10.1006/jagm.1995.1002
State	Published - Jan 1995

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.1995.1002

Cite this

@article{5833072aaa0a41119c41b8acda7e42ec,

title = "An asynchronous parallel algorithm for undirected graph connectivity",

abstract = "An algorithm for computing the components of an undirected graph in the (asynchronous) APRAM model is given; the algorithm uses O(n + e) processes and O(log n) rounds.",

author = "Richard Cole and Ofer Zajicek",

year = "1995",

month = jan,

doi = "10.1006/jagm.1995.1002",

language = "English (US)",

volume = "18",

pages = "50--97",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - An asynchronous parallel algorithm for undirected graph connectivity

AU - Cole, Richard

AU - Zajicek, Ofer

PY - 1995/1

Y1 - 1995/1

N2 - An algorithm for computing the components of an undirected graph in the (asynchronous) APRAM model is given; the algorithm uses O(n + e) processes and O(log n) rounds.

AB - An algorithm for computing the components of an undirected graph in the (asynchronous) APRAM model is given; the algorithm uses O(n + e) processes and O(log n) rounds.

UR - http://www.scopus.com/inward/record.url?scp=58149212017&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58149212017&partnerID=8YFLogxK

U2 - 10.1006/jagm.1995.1002

DO - 10.1006/jagm.1995.1002

M3 - Article

AN - SCOPUS:58149212017

SN - 0196-6774

VL - 18

SP - 50

EP - 97

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

An asynchronous parallel algorithm for undirected graph connectivity

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this