Graph / Bubble (Bibtex)

P9: Enumeration of all bubbles in a directed graph

Input:

A directed graph $G=(V, E)$ and a source $s$.

Output:

All bubbles with a given source $s$.

Complexity:

$O(|V| + |E|)$ delay with $O(|V|(|V| + |E|))$ preprocessing time.

Comment:

An $(s,t)$-bubble is two disjoint $(s,t)$-paths that only share $s$ and $t$.

Reference:

[Birmele2012] (Bibtex)

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$.

Reference:

[Sacomoto2013b] (Bibtex)