P71: Enumeration of all minimum-size separating vertex sets in a graph
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.