Parallel transitive closure and transitive reduction algorithms

Pintsang Chang; Lawrence J. Henschen

Parallel transitive closure and transitive reduction algorithms

Pintsang Chang^*, Lawrence J. Henschen

^*Corresponding author for this work

Computer Science

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

2 Scopus citations

Abstract

The authors provide distinct algorithms for computing transitive closure and transitive reduction with sequential time complexities of O(Σe_i) and O(n² + Σe_i), respectively, and parallel time complexities of O(e_i) and O(n + e_i), respectively. The proposed transitive closure algorithms are favorable for the sparse digraphs. It is still open whether transitive reduction may be computed in O(Σe_i) (or O(e_i) in parallel).

Original language	English (US)
Title of host publication	PARBASE 90 Int Conf Databases Parallel Archit Appl
Editors	Naphtali Rishe, Shamkant B. Navathe, Doron Tal
Publisher	Publ by IEEE
Pages	152-154
Number of pages	3
State	Published - Jan 1 1990
Event	PARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications - Miami Beach, FL, USA Duration: Mar 7 1990 → Mar 9 1990

Other

Other	PARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications
City	Miami Beach, FL, USA
Period	3/7/90 → 3/9/90

ASJC Scopus subject areas

Engineering(all)

Cite this

@inproceedings{765b507f89314b37bd78351a7381623f,

title = "Parallel transitive closure and transitive reduction algorithms",

abstract = "The authors provide distinct algorithms for computing transitive closure and transitive reduction with sequential time complexities of O(Σei) and O(n2 + Σei), respectively, and parallel time complexities of O(ei) and O(n + ei), respectively. The proposed transitive closure algorithms are favorable for the sparse digraphs. It is still open whether transitive reduction may be computed in O(Σei) (or O(ei) in parallel).",

author = "Pintsang Chang and Henschen, {Lawrence J.}",

year = "1990",

month = jan,

day = "1",

language = "English (US)",

pages = "152--154",

editor = "Naphtali Rishe and Navathe, {Shamkant B.} and Doron Tal",

booktitle = "PARBASE 90 Int Conf Databases Parallel Archit Appl",

publisher = "Publ by IEEE",

note = "PARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications ; Conference date: 07-03-1990 Through 09-03-1990",

}

TY - GEN

T1 - Parallel transitive closure and transitive reduction algorithms

AU - Chang, Pintsang

AU - Henschen, Lawrence J.

PY - 1990/1/1

Y1 - 1990/1/1

N2 - The authors provide distinct algorithms for computing transitive closure and transitive reduction with sequential time complexities of O(Σei) and O(n2 + Σei), respectively, and parallel time complexities of O(ei) and O(n + ei), respectively. The proposed transitive closure algorithms are favorable for the sparse digraphs. It is still open whether transitive reduction may be computed in O(Σei) (or O(ei) in parallel).

AB - The authors provide distinct algorithms for computing transitive closure and transitive reduction with sequential time complexities of O(Σei) and O(n2 + Σei), respectively, and parallel time complexities of O(ei) and O(n + ei), respectively. The proposed transitive closure algorithms are favorable for the sparse digraphs. It is still open whether transitive reduction may be computed in O(Σei) (or O(ei) in parallel).

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

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

M3 - Conference contribution

AN - SCOPUS:0025246466

SP - 152

EP - 154

BT - PARBASE 90 Int Conf Databases Parallel Archit Appl

A2 - Rishe, Naphtali

A2 - Navathe, Shamkant B.

A2 - Tal, Doron

PB - Publ by IEEE

T2 - PARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications

Y2 - 7 March 1990 through 9 March 1990

ER -

Parallel transitive closure and transitive reduction algorithms

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this