Transitive reduction of a nilpotent Boolean matrix
type: Item
instance of: scholarly article
title: Transitive reduction of a nilpotent Boolean matrix
zbMATH Open document ID: 0549.05043
DOI: 10.1016/0166-218X(84)90078-7
author: Hiroshi Hashimoto
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 06B99
zbMATH DE Number: 3875327
zbMATH Keywords: Boolean matrix
zbMATH Keywords: acyclic digraph
zbMATH Keywords: transitive reduction
zbMATH Keywords: adjacency matrix
MaRDI profile type: Publication
cites work: The Transitive Reduction of a Directed Graph
cites work: Q3903001
cites work: Matrix development of the calculus of relations
cites work: Q4770975
cites work: Q3048646
cites work: Computer construction of project networks
cites work: Q5593643
cites work: An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
cites work: Q3958592
cites work: Applications of Graphs and Boolean Matrices to Computer Programming
cites work: An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
cites work: Boolean Matrices and Logic
cites work: Q4403699
cites work: Boolean Matrix Method for the Construction of Hierarchical Graphs
cites work: On the Boolean Matrix Equation M ′ =ν i=1 M i
cites work: A Theorem on Boolean Matrices
cites work: An Efficient Algorithm for Constructing Hierarchical Graphs
cites work: Similarity relations and fuzzy orderings
description: scientific article; zbMATH DE number 3875327