P100: Enumeration of all $(s, K)$ cutsets in a graph
P100: Enumeration of all $(s, K)$ cutsets in a graph
Input:
A graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output:
All $(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{$(s, K)$ cutset} is minimal $(s, K)$ cuts.