P99: Enumeration of all quasi $(s, K)$ cuts in a directed graph
P99: Enumeration of all quasi $(s, K)$ cuts in a directed graph
Input:
A directed graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output:
All quasi $(s, K)$ cutsets in $G$.
Complexity:
$O(|E|)$ time per cut.
Comment:
An \textit{$(s, K)$-cut} is defined to be any cut $(X, Y)$ for which $s \in X$ and $K \cap Y \neq \emptyset$. A \textit{Quasi $(s, K)$ cut} is an edge set that is strong $(s, A)$-cutsets for some $A \subseteq K$ and $A \neq \emptyset$.