# Re: Incremental computation of dominators

## Luis Quesada <luque@info.ucl.ac.be>16 Aug 2005 11:13:20 -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: 16 Aug 2005 11:13:20 -0400 Organization: Compilers Central References: 05-08-049 Keywords: analysis Posted-Date: 16 Aug 2005 11:13:20 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?

@Article{lengauer79,
author = {T. Lengauer and R. Tarjan},
title = {A Fast Algorithm for Finding Dominators in a Flowgraph},
journal = {ACM Transactions on Programming Languages and Systems},
year = {1979},
}

> 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.

I found this other article that addresses this issue:

@article{sreedhar97incremental,
author = "Vugranam C. Sreedhar and Guang R. Gao and Yong-Fong Lee",
title = "Incremental Computation of Dominator Trees",
journal = "ACM Transactions on Programming Languages and Systems",
volume = "19",
number = "2",
month = "March",
publisher = "ACM Press",
pages = "239--252",
year = "1997",
url = "citeseer.ist.psu.edu/sreedhar95incremental.html" }

Once again, many thanks to Eugene Ressler for pushing me in the right
direction!

Luis

Post a followup to this message