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

P319: 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|/\log|V|)$ total time.

Comment:

$R_{ab}$ is the number of minimal $a$-$b$ separators. This algorithm needs $O(|V|^3)$ processors on a CREW PRAM.

Reference:

[Shen1997] (Bibtex)