PARALLEL ALGORITHM FOR DOMINATORS.

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

PARALLEL ALGORITHM FOR DOMINATORS.

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

Computer Science

Stony Brook University

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

A fast parallel algorithm is presented for computing the dominators of a directed acyclic graph. The model of computation used is a parallel random access machine which 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 acyclic graph on this model. The algorithm for computing the dominators requires O(log**2 n) time using O(P//t (n)) processors. The only known parallel algorithm for this problem requires O(nP//t (n)) processors. The authors' algorithm therefore improves on the processor complexity of this algorithm by a factor of n, but has the same time complexity.

Original language	English
Title of host publication	Proceedings of the International Conference on Parallel Processing
Editors	Kai Hwang, Steven M. Jacobs, Earl E. Swartzlander
Publisher	IEEE
Pages	877-879
Number of pages	3
ISBN (Print)	0818607246
State	Published - 1986

Publication series

Name	Proceedings of the International Conference on Parallel Processing

Cite this

@inproceedings{ab61a37d344e4eccaa1fa9c88b9645c1,

title = "PARALLEL ALGORITHM FOR DOMINATORS.",

abstract = "A fast parallel algorithm is presented for computing the dominators of a directed acyclic graph. The model of computation used is a parallel random access machine which 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 acyclic graph on this model. The algorithm for computing the dominators requires O(log**2 n) time using O(P//t (n)) processors. The only known parallel algorithm for this problem requires O(nP//t (n)) processors. The authors' algorithm therefore improves on the processor complexity of this algorithm by a factor of n, but has the same time complexity.",

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

year = "1986",

language = "English",

isbn = "0818607246",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "IEEE",

pages = "877--879",

editor = "Kai Hwang and Jacobs, \{Steven M.\} and Swartzlander, \{Earl E.\}",

booktitle = "Proceedings of the International Conference on Parallel Processing",

}

PARALLEL ALGORITHM FOR DOMINATORS. / Pawagi, Shaunak; Gopalakrishnan, P. S.; Ramakrishnan, I. V.
Proceedings of the International Conference on Parallel Processing. ed. / Kai Hwang; Steven M. Jacobs; Earl E. Swartzlander. IEEE, 1986. p. 877-879 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - PARALLEL ALGORITHM FOR DOMINATORS.

AU - Pawagi, Shaunak

AU - Gopalakrishnan, P. S.

AU - Ramakrishnan, I. V.

PY - 1986

Y1 - 1986

N2 - A fast parallel algorithm is presented for computing the dominators of a directed acyclic graph. The model of computation used is a parallel random access machine which 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 acyclic graph on this model. The algorithm for computing the dominators requires O(log**2 n) time using O(P//t (n)) processors. The only known parallel algorithm for this problem requires O(nP//t (n)) processors. The authors' algorithm therefore improves on the processor complexity of this algorithm by a factor of n, but has the same time complexity.

AB - A fast parallel algorithm is presented for computing the dominators of a directed acyclic graph. The model of computation used is a parallel random access machine which 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 acyclic graph on this model. The algorithm for computing the dominators requires O(log**2 n) time using O(P//t (n)) processors. The only known parallel algorithm for this problem requires O(nP//t (n)) processors. The authors' algorithm therefore improves on the processor complexity of this algorithm by a factor of n, but has the same time complexity.

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

M3 - Conference contribution

SN - 0818607246

T3 - Proceedings of the International Conference on Parallel Processing

SP - 877

EP - 879

BT - Proceedings of the International Conference on Parallel Processing

A2 - Hwang, Kai

A2 - Jacobs, Steven M.

A2 - Swartzlander, Earl E.

PB - IEEE

ER -

PARALLEL ALGORITHM FOR DOMINATORS.

Abstract

Publication series

Other files and links

Fingerprint

Cite this