P235: Enumeration of all $k$-outconnected minimal spanning graph
P235: Enumeration of all $k$-outconnected minimal spanning graph
Input:
A graph $G = (V, E)$, a vertex $s \in V$, and an integer $k$.
Output:
All minimal $k$-outconneted from $s$ spanning subgraph of $G$.
Complexity:
Incremental polynomial time.
Comment:
A graph is $k$-outconnected from $s$ if it contains $k$ internally-disjoint $st$-paths for every $t \in V$. This complexity holds for both vertex and edge-connectivity.