3.7.246. 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.75 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.75. (A)ย A connected digraph, (B)ย its three strongly connected components ๐‘ ๐‘๐‘ 1 , ๐‘ ๐‘๐‘ 2 and ๐‘ ๐‘๐‘ 3 when its unique strong articulation point (i.e.,ย the vertex labelled by 3) is removed
ctrs/preface-213-tikz