Re: Incremental computation of dominators

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:


@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

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