Re: finding all dominator trees

s1l3ntr3p wrote:
> Amir Michail wrote:
> > diablovision@yahoo.com wrote:
> > > > Is there an efficient algorithm for finding all dominator trees of a
> > > > graph? That is, for every node, find its dominator tree. I'm looking
> > > > for something better than simply running a dominator tree algorithm
> > > > for each node in the graph.
> > >
> > > Unless I am missing some subtlety of your situation, you should just be
> > > able to run the dominator tree algorithm for the root node of the
> > > graph. Dominator trees have the property that each subtree for a node
> > > corresponds to the dominator tree for that node.
> > >
> >
> > There is no root. This is an arbitrary graph.
> >
> > Amir
> >
> > > See "Efficiently Computing Static Single Assignment Form and the
> > > Control Dependence Graph" by Cytron et al.
>
>
> This is from Torczon's book: "In a CFG, node i <dominates> node j if
> every path from the entry node to j passes through i". What this tells
> us is that we need a root (entry) node.


The idea is to consider each node in turn as a root and build a
dominator tree with respect to that root. A naive way to do this is to
run a dominator tree algorithm for each such root separately.


But maybe there's a more efficient way (even though the relationship
between these dominator trees may not be obvious in general).


The application here has nothing to do with compilers: I would like to
compute a dominator tree for each person in a social network to build
a better social news service:


http://targetyournews.com/ajax/TargetYourNews.html>md%3DMore%26link_id%3D656584


Amir

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