P72: Enumeration of all minimal $a$-$b$ separators in a graph

P72: Enumeration of all minimal $a$-$b$ separators in a graph

Input:

An undirected connected simple graph $G = (V, E)$, non-adjacent vertices $a$ and $b$ in $G$.

Output:

All minimal $a$-$b$ separator of $G$.

Complexity:

$O(R_{ab}|V|^3)$ total time.

Comment:

$R_{ab}$ is the number of minimal $a$-$b$ separators.

Reference:

[Shen1997] (Bibtex)