Accession Number:

ADA022161

Title:

On Computing the Transitive Closure of a Relation,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1975-09-01

Pagination or Media Count:

16.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE