I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
-
1$\begingroup$ Have you checked Wikipedia? ps: have you read our FAQ? $\endgroup$– KavehJun 1, 2013 at 22:54
-
7$\begingroup$ The Wikipedia article you link to is only about undirected graphs, so it doesn't answer Yossi's question. $\endgroup$– David EppsteinJun 2, 2013 at 0:24
-
$\begingroup$ @David, I see. Does biconnected component in the case of directed graphs mean that the graph will remain strongly connected after the removal of any vertex from the component? $\endgroup$– KavehJun 2, 2013 at 1:20
-
2$\begingroup$ That's what I would guess, and a search of Google scholar for "k-strongly-connected" finds some sources using that definition, but other sources using an edge connectivity version in which each nontrivial subset of the vertices has at least k incoming edges. $\endgroup$– David EppsteinJun 2, 2013 at 3:47