P237: Enumeration of all $k$-connected minimal spanning graph

P237: Enumeration of all $k$-connected minimal spanning graph

Input:

A directed graph $G = (V, E)$ and an integer $k$.

Output:

All minimal $k$-connected spanning subgraph of $G$.

Complexity:

Incremental polynomial time.

Comment:

This complexity holds for both vertex and edge-connectivity.

Reference:

[Nutov2009] (Bibtex)