An algorithm for transitive reduction of an acyclic graph (Q1124350)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4112034
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An algorithm for transitive reduction of an acyclic graph |
scientific article; zbMATH DE number 4112034 |
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
0.9120444
0 references
0.8945611
0 references
0.88904184
0 references
0.8844303
0 references
0.8791708
0 references
0.8720337
0 references
