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