P95: Enumeration of all semidirected $(s, t)$ cuts in a directed graph
P95: Enumeration of all semidirected $(s, t)$ cuts in a directed graph
Input:
A directed graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output:
All semidirected $(s, t)$ cuts in $G$.
Complexity:
$O(|V||E|)$ time per cut.
Comment:
For a subset $D$ of directed edges, a \textit{semidirected $(s, t)$ cut} with respect to $D$ is an $(s, t)$ cut $(X, Y)$ such that $(X, Y) \cup (Y, X)$ defnes an undirected $(s, t)$ cutset and such that $(X, Y) \cap D = \emptyset$, where a \textit{cutset} is an minimal cut set.