An algorithm for transitive reduction of an acyclic graph (Q1124350)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An algorithm for transitive reduction of an acyclic graph |
scientific article |
Statements
An algorithm for transitive reduction of an acyclic graph (English)
0 references
1989
0 references
A simple \(0(N^ 3)\) algorithm for computing the transitive reduction of an acyclic digraph is presented. It operates by first computing the transitive closure and then removing in essential arcs. The correctness of the algorithm admits a short proof.
0 references
transitive reduction
0 references
acyclic digraph
0 references
transitive closure
0 references
