3.7.233. Strong bridge

A constraint for which the filtering algorithm may use the notion of strong bridge (i.e., enforce arcs corresponding to strong bridges to be part of the solution in order to avoid creating too many strongly connected components). A strong bridge of a strongly connected digraph $G$ is an arc such that, if we remove it, $G$ is broken into at least two strongly connected components. Figure 3.7.63 illustrates the notion of strong bridge on the digraph depicted by part (A). The arc from the vertex labelled by 2 to the vertex labelled by 1 is a strong bridge since its removal creates the three strongly connected components depicted by part (B) (i.e., the first, second and third strongly connected components correspond respectively to the sets of vertices $\left\{1,3,4\right\}$, $\left\{2\right\}$ and $\left\{5\right\}$). The other strong bridges of the digraph depicted by part (A) are the arcs $1\to 3$ and $5\to 2$. From an algorithmic point of view, it was shown in [ItalianoLauraSantaroni10] how to compute all the strong bridges of a digraph $G$ in linear time with respect to the number of arcs of $G$.