Re: Computing cut nodes and bridges in directed graphs

Luis Quesada wrote:

T1:=DFS(RemoveVertex(T0,i),source) 

I meant T1:=DFS(RemoveVertex(g,i),source)

T0:=DFS(g,source)
for e \in edges(g) do
   BE(e):= if e \in edges(T0) then \emptyset else edges(g) end
end
for e1 \in edges(T0) do
   T1:=DFS(RemoveEdge(T0,e1),source)
   for e2 \in edges(T0)-edges(T1) do
      BE(e2):=BE(e2) \cup {e1}
   end
end


I meant:

T0:=DFS(g,source)
for i \in vertexes(g) do
   BE(i):= if i \in vertexes(T0) then \emptyset else edges(g) end
end
for e \in edges(T0) do
   T1:=DFS(RemoveEdge(g,e),source)
   for i \in vertexes(T0)-vertexes(T1) do
      BE(i):=BE(i) \cup {e}
   end
end

Sorry for the mistakes! (I hope to have gotten it right now :-))

Anyway, after I sent the previous message I also realized that a first approximation to the incremental algorithm I am looking for is the one where we take into account the fact that cut nodes and bridges are always part of the reachability tree. So, in order to update CN/BE after removing a set of edges, I only need to look at the vertexes/edges that belong to

Gdelta=DFS(g',source)-DFS(g,source)

where g' is the graph that we obtain from g after removing the edges.

Luis
.