P93: Enumeration of all $(s, t)$-uniformly directed cuts in a directed graph
P93: Enumeration of all $(s, t)$-uniformly directed cuts in a directed graph
Input:
A directed graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output:
All $(s, t)$-uniformly directed cuts in $G$.
Complexity:
$O(|V|)$ time per cut.
Comment:
An \textit{undirected directed cut} is also called a UDC. An $(s, t)$-DUC is an $(s, t)$-cut $(X, Y)$ such that $(X, Y) = \emptyset$, where $(X, Y) = \{(u, v) \in E: u\in X, v\in Y\}$.