P9: Enumeration of all bubbles in a directed graph

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)