P135: Enumeration of all cut conjunctions of a graph
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)$.