Re: Computing cut nodes and bridges in directed graphs

Dear Googmeister,


Yes, there are linear-time algorithms due to Tarjan and others.
Google for "strongly connected components."

Not sure I understand how the computation of strongly connected components can help me since I am dealing with directed graph. We can come up with graphs having one component and several cut nodes. For instance, consider the following graph g=<{1,2,3},{<1,2>,<2,3>,<3,1>}>. There is only one component but 1, 2 and 3 are cut nodes in particular contexts (i.e., 1 \in CutNode(g,3,2), 2 \in CutNode(g,1,3) and 3 \in CutNode(g,2,1)).

Could you elaborate more on the approach you are suggesting, please?

I don't know the state-of-the art on the version with
insertions/deletions,
but the problem is known as "dynamic" strongly connected components
or "incremental" / "decremental" if you only allow insertions or
deletions.


I have already gotten in touch with some people working on dynamic graph algorithms. It seems that the case of directed graph has not been studied that much.

Luis
.