BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-508
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On computing the transitive closure of a relation.
        TYPE:: Technical Report
      AUTHOR:: Eve, James
        DATE:: September 1975
       PAGES:: 15
    ABSTRACT:: An algorithm is presented for computing the transitive
               closure of an arbitrary relation which is based upon a
               variant of Tarjan's algorithm [1972] for finding the strongly
               connected components of a directed graph. This variant leads
               to a more compact statement of Tarjan's algorithm.

               If V is the number of vertices in the directed graph
               representing the relation then the worst case behavior of the
               proposed algorithm involves O($V^3$) operations. In this
               respect it is inferior to existing algorithms which require
               O($V^3$/log V) and O($V^{{log}_2 7}$ log V) operations
               respectively. The best case behavior involves only O($V^2$)
               operations.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-508