Parallel transitive closure and transitive reduction algorithms

Pintsang Chang*, Lawrence J. Henschen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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).

Original languageEnglish (US)
Title of host publicationPARBASE 90 Int Conf Databases Parallel Archit Appl
EditorsNaphtali Rishe, Shamkant B. Navathe, Doron Tal
PublisherPubl by IEEE
Pages152-154
Number of pages3
StatePublished - Jan 1 1990
EventPARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications - Miami Beach, FL, USA
Duration: Mar 7 1990Mar 9 1990

Other

OtherPARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications
CityMiami Beach, FL, USA
Period3/7/903/9/90

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Chang, P., & Henschen, L. J. (1990). Parallel transitive closure and transitive reduction algorithms. In N. Rishe, S. B. Navathe, & D. Tal (Eds.), PARBASE 90 Int Conf Databases Parallel Archit Appl (pp. 152-154). Publ by IEEE.