Finding strong bridges and strong articulation points in linear time

Abstract: Given a directed graph , an edge is a strong bridge if its removal increases the number of strongly connected components of . Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of . In this paper, we present linear-time algorithms for computing all the strong bridges and all the strong articulation points of directed graphs, solving an open problem posed in Beldiceanu et al. (2005) . [Copyright &y& Elsevier]