On Computing the Transitive Closure of a Relation,

reportActive / Technical Report | Accession Number: ADA022161 | Need Help?

Abstract:

An algorithm is presented for computing the transitive closure of an arbitrary relation which is based upon a variant of Tarjans algorithm for finding the strongly connected components of a directed graph. This variant leads to a more compact statement of Tarjans algorithm.

Author(s):
Eve, James
Author Organization(s):
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination:
0016

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
STAN-CS-75-508
Contract/Grant Number(s):
N00014-67-A-0112-0057, NSF-DCR72-03752-A02
Project Number(s):
NR-044-402
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*RECURSIVE FUNCTIONS, *SET THEORY, ALGORITHMS, COMPUTATIONS, BOOLEAN ALGEBRA
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
Parsing, *Graph theory
Report Date:
1975 Sep 01