A modification of Warshall's algorithm for the transitive closure of binary relations

1 April 1975

journal article
Published by Association for Computing Machinery (ACM) in Communications of the ACM

Vol. 18 (4) , 218-220
https://doi.org/10.1145/360715.360746

Abstract

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.

Keywords

BOOLEAN MATRIX
WARSHALL'S ALGORITHM
BINARY RELATION
DIGRAPH
DIRECTED GRAPH
REACHABILITY MATRIX
TRANSITIVE CLOSURE

This publication has 4 references indexed in Scilit:

A transitive closure algorithm
BIT Numerical Mathematics, 1970
An algorithm for computing all paths in a graph
BIT Numerical Mathematics, 1966
A note on multiplying Boolean matrices
Communications of the ACM, 1962
A Theorem on Boolean Matrices
Journal of the ACM, 1962