I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
Asked
Viewed
646 times
6
$\begingroup$
$\endgroup$
-
1$\begingroup$ Have you checked Wikipedia? ps: have you read our FAQ? $\endgroup$ – Kaveh Jun 1 '13 at 22:54
-
5$\begingroup$ The Wikipedia article you link to is only about undirected graphs, so it doesn't answer Yossi's question. $\endgroup$ – David Eppstein Jun 2 '13 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$ – Kaveh Jun 2 '13 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 Eppstein Jun 2 '13 at 3:47
