P191: Enumeration of all $(s, t, \alpha_1, \alpha_2)$-bubble in a directed graph
P191: Enumeration of all $(s, t, \alpha_1, \alpha_2)$-bubble in a directed graph
Input:
A directed graph $G = (V, E)$, source vertex $s$, and two upper bounds $\alpha_1$ and $\alpha_2$.
Output:
All $(s, t, \alpha_1, \alpha_2)$-bubble in $G$.
Complexity:
$O(|V|(|E|+|V|\log |V|))$ delay.
Comment:
A pair of two vertex-disjoint $(s, t)$-paths $p_1$ and $p_2$ is $(s, t, \alpha_1, \alpha_2)$-bubble in $G$, if $|p_1| \le \alpha_1$ and $|p_2| \le \alpha_2$.