3.7.234. Strong articulation point

A constraint for which the filtering algorithm uses the notion of strong articulation point. A strong articulation point of a strongly connected digraph G is a vertex such that if we remove it, G is broken into at least two strongly connected components. FigureΒ 3.7.64 illustrates the notion of strong articulation point on the digraph depicted by partΒ (A). The vertex labelled by 3 is a strong articulation point 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 {1,4}, {2} and {5}). From an algorithmic point of view, it was shown inΒ [ItalianoLauraSantaroni10] how to compute all the strong articulation points of a digraph G in linear time with respect to the number of arcs of G.

Figure 3.7.64. A connected digraph and its strongly articulation point