All Maximal Non-Branching Paths in a Graph (All Maximal Non-Branching Paths in a Graph)
Jump to navigation
Jump to search
Description
A node $v$ in a directed graph $G$ is called a 1-in-1-out node if its indegree and outdegree are both equal to 1, i.e., $in(v) = out(v) = 1$. We can rephrase the definition of a "maximal non-branching path" from the main text as a path whose internal nodes are 1-in-1-out nodes and whose initial and final nodes are not 1-in-1-out nodes.
The problem is to find all maximal non-branching paths in a given graph.
Parameters
n: number of vertices
m: number of edges
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Naive | 1940 | $O(m)$ | $O(n)$ auxiliary? | Exact | Deterministic | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
