Naive (All Maximal Non-Branching Paths in a Graph All Maximal Non-Branching Paths in a Graph)
Jump to navigation
Jump to search
Time Complexity
$O(m)$
Space Complexity
$O(n)$? words
(For each vertex, store whether that vertex is a 1-in-1-out vertex (all of these can be pre-computed at the same time in $O(m)$ time). Unclear if there's a better bound)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1940