A theorem on Boolean matrices

Warshall, S. (1962). A theorem on Boolean matrices. Journal of the ACM, 9(1), 11-12.

Type

Journal article

Intellectual base

Primary research

Year

1962

DOI

10.1145/321105.321107

Link

https://doi.org/10.1145/321105.321107

Cited from

mathematics

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Primes

• Closure
  • Transitive closure is a primitive of graph theory and of recursive query languages (SQL WITH RECURSIVE and Datalog), with the transitive-closure operator computing the smallest transitive relation containing a given relation, an algorithm Warshall (1962) gives in its canonical \(O(n^3)\) form.

    This sourceOriginating presentation of the $O(n^3)$ algorithm for the transitive closure of a binary relation (reachability matrix of a directed graph).

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:5f332db059df · see in the full table