Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem)
Jump to navigation
Jump to search
Time Complexity
$O(n^{3})$
Space Complexity
$O(n^{2})$ words
(Generally keeps track of O(1) information for every pair (u, v) of vertices? and not much additional information needed)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1989
Reference
https://www.sciencedirect.com/science/article/pii/0167642389900397