Re: Computing cut nodes and bridges in directed graphs


Luis Quesada wrote:
> Dear all,
>
> I am currently working on the implementation of a propagator for solving
> constrained path problem (
> www.info.ucl.ac.be/~luque/CICLOPS2005/paper.pdf). The propagator is
> based on the computation of cut nodes and bridges in *directed* graphs [*].
>
> Currently, the computation of cut nodes and bridge is quite
> simple/naive: given a graph g and a source node s, I need to compute the
> cut nodes between s and any other node of g. What I do is to run DFS per
> each potential cut node. So the computation of all the sets of cut nodes
> is O(V*(V+E)). I use a similar approach for computing bridges whose
> complexity is O(E*(V+E)). Is there a more efficient way of doing this?

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

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.

.