P71: Enumeration of all minimum-size separating vertex sets in a graph
Input:
A graph $G = (V, E)$.
Output:
All minimum-size separating vertex sets.
Complexity:
$\Theta(M|V| + C) = O(2^kn^3)$ total time.
Comment:
$M$ is the number of solutions, $k$ is the connectivity of $G$, and $C = k|V| \min(k(|V|+|E|), A)$, where $A$ is the time complexity of the best maximum network flow algorithm for unit network.
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\}$.
P95: Enumeration of all semidirected $(s, t)$ cuts in a directed graph
Input:
A directed graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output:
All semidirected $(s, t)$ cuts in $G$.
Complexity:
$O(|V||E|)$ time per cut.
Comment:
For a subset $D$ of directed edges, a \textit{semidirected $(s, t)$ cut} with respect to $D$ is an $(s, t)$ cut $(X, Y)$ such that $(X, Y) \cup (Y, X)$ defnes an undirected $(s, t)$ cutset and such that $(X, Y) \cap D = \emptyset$, where a \textit{cutset} is an minimal cut set.
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$.
P97: Enumeration of all strong $(s, K)$ cutsets in a directed graph
Input:
A directed 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$.
P98: Enumeration of all quasi $(s, K)$ cuts in a graph
Input:
A 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$.
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$.
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.
P281: Enumeration of all cut conjunctions for a given set of vertex pairs in a graph
Input:
A graph $G = (V,E)$, and a collection $B = \{(s_1,t_1),...,(s_k,t_k)\}$ of $k$ vertex pairs $s_i,t_i \in V$.
Output:
All cut conjunctions for $B$ in $G$.
Complexity:
Incremental polynomial time.
Comment:
A minimal edge sets $X \subseteq E$ is a \textit{cut conjunction} if, for all $i = 1, \dots, k$, vertices $s_i$ and $t_i$ is disconnected in $G' = (V, E\setminus X)$. A cut conjunction is a generalization of an $s-t$ cut.
P135: Enumeration of all cut conjunctions of a graph
Input:
A graph $G = (V, E)$ and a collection $B = \{(s_1, t_1), \dots, (s_k, t_k)\}$.
Output:
All cut conjunctions of $G$.
Complexity:
$O(K^2 \log(K) |V||E|^2 + K^2|B|(|V|+|E|)|E|^2)$ total time.
Comment:
$K$ is the number of cut conjunctions. $X$ is a cut conjunctions of $G$ if $X$ is a minimal edge set such that for all $i = 1, \dots, k$, a pair of vertices $s_i$ and $t_i$ is disconnected in $(V, E\setminus X)$.