P136: Enumeration of all bridge-avoiding extensions of a graph
P136: Enumeration of all bridge-avoiding extensions of a graph
Input:
A graph $G = (V, E)$ and an edge subset $B \subseteq E$.
Output:
All bridge-avoiding extensions of $G$.
Complexity:
$O(K^2 \log(K) |E|^2 + K^2(|V|+|E|)|E|^2)$ total time.
Comment:
$K$ is the number of bridge-avoiding extensions. $X$ is a bridge-avoiding extensions of $G$ if $X$ is a minimal edge set $X \subseteq E \setminus B$ such that no edge $b \in B$ is a bridge in $(V, B\cup X)$.