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$
    – Kaveh
    Commented Jun 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$ Commented Jun 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$
    – Kaveh
    Commented Jun 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$ Commented Jun 2, 2013 at 3:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.