P138: Enumeration of all minimal $k$-vertex connected spanning subgraphs in a $k$-connected graph.

P138: Enumeration of all minimal $k$-vertex connected spanning subgraphs in a $k$-connected graph.

Input:

A $k$-connected graph $G$.

Output:

All minimal $k$-vertex connected spanning subgraphs in $G$.

Complexity:

$O(K^3|E|^3|n| + K^2|E|^5|V|^4 + K|V|^k|E|^2)$ total time.

Comment:

$K$ is the number of solutions. A graph $G$ is $k$-connected if a subgraph of $G$ obtained by removing at most $k-1$ vertices is still connected.

Reference:

[Boros2007] (Bibtex)