All Maximal Non-Branching Paths in a Graph (All Maximal Non-Branching Paths in a Graph)

From Algorithm Wiki
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)$? Exact Deterministic Time

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination