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$.

Reference:

[Provan1996] (Bibtex)