Incremental computation of dominators

Dear all,


I need to compute the vector CN, where CN(i)=CutNodes(g,source,i) (i.e.,
the set of vertexes appearing in all paths from source to i in the
directed graph g). The algorithm that I currently have is the following:


T0:=DFS(g,source)
for i \in vertexes(g) do
      CN(i):= if i \in vertexes(T0) then \emptyset else vertexes(g) end
end
for i \in vertexes(T0) do
      T1:=DFS(RemoveVertex(g,i),source)
      for j \in vertexes(T0)-vertexes(T1) do
            CN(j):=CN(j) \cup {i}
      end
end


Assume that DFS returns the reachability tree. CN(i) is initialized with
\emptyset or vertexes(g) depending on whether i is reached from the
source (the point is that, under our definition, any vertex is a cut
node between the source and i if i is not reached from the source).
Then, we simply try each potential cut node and update the corresponding
sets. So our computation of cut nodes is O(V*(V+E)).


Eugene Ressler (in comp.theory) made me realize that I am actually
computing dominators. So, my first question is: is my current approach
efficient?


I am also looking for an incremental approach since I don't want to
recompute this information from scratch whenever a set of edges is
removed. One alternative could be to come up with an incremental
implementation of DFS (since we only need to look at the DFS tree).
However, I still don't know how to implement DFS incrementally.


Thanks in advance for your help!


Luis

Return to the comp.compilers page.
Search the comp.compilers archives again.