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 Jun 1 '13 at 22:54
  • 6
    $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.