Re: Incremental computation of dominators

Luis Quesada <>
16 Aug 2005 11:13:20 -0400

          From comp.compilers

Related articles
Incremental computation of dominators (Luis Quesada) (2005-08-13)
Re: Incremental computation of dominators (Luis Quesada) (2005-08-16)
Re: Incremental computation of dominators (Jeff Kenton) (2005-08-24)
Re: Incremental computation of dominators (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

Luis Quesada wrote:
> 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 found this article that answers this question:

      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:

          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 = "" }

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


Post a followup to this message

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