Given a directed graph G, an edge is a strong bridge if its removal increases the number of strongly connected components of G. Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of G. 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).
Finding strong bridges and strong articulation points in linear time / G. F., Italiano; Laura, Luigi; F., Santaroni. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 447:(2012), pp. 74-84. [10.1016/j.tcs.2011.11.011]
Finding strong bridges and strong articulation points in linear time.
LAURA, Luigi;
2012
Abstract
Given a directed graph G, an edge is a strong bridge if its removal increases the number of strongly connected components of G. Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of G. 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).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
