Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem)
Revision as of 12:17, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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")
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