A Modification of Warshall's Algorithm for
the Transitive Closure of Binary Relations

An algorithm is given for computing the transitive
closure of a binary relation that is represented 
by a Boolean matrix. The algorithm is similar to Warshall's
although it executes faster for sparse matrices
on most computers, particularly in a paging environment.

CACM April, 1975

Warren, H. S. Jr.

Warshall's algorithm, transitive closure, reachability
matrix, directed graph, digraph, Boolean 
matrix, binary relation

5.30 5.32

CA750408 JB January 9, 1978  3:49 PM

1151	4	2769
1265	4	2769
2769	4	2769
2769	5	2769
2769	5	2769
2769	5	2769
635	5	2769