Computing cut nodes and bridges in directed graphs

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?

I am also interested in an incremental approach for computing this information. I.e., given a graph g, a source node s, and a function cn that associates each pair <s,i> with its corresponding cut nodes, how can I update this information when a set of edges is removed without starting from scratch? (Similar question for bridges).

Thanks in advance for your help,

Luis

[*] The use of the terms cut node and bridge may be misleading since these terms are normally used when dealing with undirected graph. The definition I am using is the following: a node k/an edge e is a cut node/bridge between two nodes i and j, if k/e appears in all paths from i to j.


.