7
$\begingroup$

I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Have you checked Wikipedia? ps: have you read our FAQ? $\endgroup$
    – Kaveh
    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$
    – David Eppstein
    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
    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$
    – David Eppstein
    Jun 2, 2013 at 3:47

0

Reset to default

Your Answer

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