# Incremental computation of dominators

## Luis Quesada <luque@info.ucl.ac.be>13 Aug 2005 00:24:31 -0400

From comp.compilers

Related articles
Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-13)
Re: Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-16)
Re: Incremental computation of dominators jeffrey.kenton@comcast.net (Jeff Kenton) (2005-08-24)
Re: Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-31)
| List of all articles for this month |

 From: Luis Quesada Newsgroups: comp.compilers Date: 13 Aug 2005 00:24:31 -0400 Organization: -= Belgacom Usenet Service =- Keywords: analysis, question Posted-Date: 13 Aug 2005 00:24:31 EDT

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.