Re: Computing cut nodes and bridges in directed graphs


Luis Quesada wrote:
> 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)).

Sorry, I misunderstood and was working from a different definition
of cut node.

.