Transitive reduction of a nilpotent Boolean matrix
Given an acyclic digraph, a problem which frequently arises in applications consists in removing the maximum number of arcs without affecting reachability. This removal corresponds to a so-called transitive reduction of the adjacency matrix of the given digraph. Regarded as a Boolean matrix, the adjacency matrix of an acyclic digraph is nilpotent and the transitive reduction is easily obtained in the context of Boolean algebra. This paper gives a very good and compact presentation of the main properties of the transitive reduction, some of them known (like theorem 1 which was tacitly used by this reviewer in the paper quoted in the references) but here elegantly and explicitly reformulated. The list of references is fairly complete.
scientific article; zbMATH DE number 3875327
scientific article