Computing dominators in parallel

Shaunak R. Pawagi; P. S. Gopalakrishnan; I. V. Ramakrishnan

doi:10.1016/0020-0190(87)90136-0

Computing dominators in parallel

Shaunak R. Pawagi
, P. S. Gopalakrishnan
, I. V. Ramakrishnan

Computer Science

Stony Brook University

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

11 Scopus citations

Abstract

We present a fast parallel algorithm for computing the dominators of a directed acyclic graph. The model of computation used in a parallel random access machine that allows simultaneous reads but prohibits simultaneous writes into the same memory location. Let P_t(n) be the processor complexity of computing the transitive closure of an n-vertex directed graph on this model. The only known parallel algorithm for dominators requires O(log²n) time and uses O(nP_t(n)) processors. Our algorithm for dominators has the same time complexity but uses O(P_t(n)) processors, thereby improving the processor complexity of the previously known algorithm by a factor of n.

Original language	English
Pages (from-to)	217-221
Number of pages	5
Journal	Information Processing Letters
Volume	24
Issue number	4
DOIs	https://doi.org/10.1016/0020-0190(87)90136-0
State	Published - Mar 2 1987

Keywords

Parallel algorithm
dominator
transitive closure

Access to Document

10.1016/0020-0190(87)90136-0

Cite this

@article{abeb0f0b07084d8d91f7532ccafd25ca,

title = "Computing dominators in parallel",

abstract = "We present a fast parallel algorithm for computing the dominators of a directed acyclic graph. The model of computation used in a parallel random access machine that allows simultaneous reads but prohibits simultaneous writes into the same memory location. Let Pt(n) be the processor complexity of computing the transitive closure of an n-vertex directed graph on this model. The only known parallel algorithm for dominators requires O(log2n) time and uses O(nPt(n)) processors. Our algorithm for dominators has the same time complexity but uses O(Pt(n)) processors, thereby improving the processor complexity of the previously known algorithm by a factor of n.",

keywords = "Parallel algorithm, dominator, transitive closure",

author = "Pawagi, \{Shaunak R.\} and Gopalakrishnan, \{P. S.\} and Ramakrishnan, \{I. V.\}",

year = "1987",

month = mar,

day = "2",

doi = "10.1016/0020-0190(87)90136-0",

language = "English",

volume = "24",

pages = "217--221",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Computing dominators in parallel

AU - Pawagi, Shaunak R.

AU - Gopalakrishnan, P. S.

AU - Ramakrishnan, I. V.

PY - 1987/3/2

Y1 - 1987/3/2

N2 - We present a fast parallel algorithm for computing the dominators of a directed acyclic graph. The model of computation used in a parallel random access machine that allows simultaneous reads but prohibits simultaneous writes into the same memory location. Let Pt(n) be the processor complexity of computing the transitive closure of an n-vertex directed graph on this model. The only known parallel algorithm for dominators requires O(log2n) time and uses O(nPt(n)) processors. Our algorithm for dominators has the same time complexity but uses O(Pt(n)) processors, thereby improving the processor complexity of the previously known algorithm by a factor of n.

AB - We present a fast parallel algorithm for computing the dominators of a directed acyclic graph. The model of computation used in a parallel random access machine that allows simultaneous reads but prohibits simultaneous writes into the same memory location. Let Pt(n) be the processor complexity of computing the transitive closure of an n-vertex directed graph on this model. The only known parallel algorithm for dominators requires O(log2n) time and uses O(nPt(n)) processors. Our algorithm for dominators has the same time complexity but uses O(Pt(n)) processors, thereby improving the processor complexity of the previously known algorithm by a factor of n.

KW - Parallel algorithm

KW - dominator

KW - transitive closure

UR - https://www.scopus.com/pages/publications/0023642119

U2 - 10.1016/0020-0190(87)90136-0

DO - 10.1016/0020-0190(87)90136-0

M3 - Article

SN - 0020-0190

VL - 24

SP - 217

EP - 221

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

Computing dominators in parallel

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this