Re: Computing cut nodes and bridges in directed graphs
- From: Luis Quesada <luque@xxxxxxxxxxxxxx>
- Date: Thu, 11 Aug 2005 10:10:27 +0200
Gene wrote:
Dear Gene,Luis, Now that I understand better what you are trying to do, I think you want to look at the literature on dominators and dominator graphs. These are most often used in compiler optimizations.
I think you are absolutely right. Indeed, j \in CutNode(g,source,i) means that j dominates i!
Certainly, computing cut nodes and bridges reduces to computing the dominators in the graph that we obtain from mapping the original edges to vertexes (and connecting the new vertexes accordingly).
Thanks a lot for pushing me in this direction!
Kind regards,
Luis
PS: I think I will raise the issue in comp.compilers too!
.
- References:
- Computing cut nodes and bridges in directed graphs
- From: Luis Quesada
- Re: Computing cut nodes and bridges in directed graphs
- From: Gene
- Re: Computing cut nodes and bridges in directed graphs
- From: Luis Quesada
- Re: Computing cut nodes and bridges in directed graphs
- From: Gene
- Re: Computing cut nodes and bridges in directed graphs
- From: Luis Quesada
- Re: Computing cut nodes and bridges in directed graphs
- From: Luis Quesada
- Re: Computing cut nodes and bridges in directed graphs
- From: Gene
- Re: Computing cut nodes and bridges in directed graphs
- From: Luis Quesada
- Re: Computing cut nodes and bridges in directed graphs
- From: Gene
- Computing cut nodes and bridges in directed graphs
- Prev by Date: Re: Efficient way to store an isomorphism?
- Next by Date: Re: asymptotic behaviour of multivariate recurrence equations?
- Previous by thread: Re: Computing cut nodes and bridges in directed graphs
- Next by thread: Re: Computing cut nodes and bridges in directed graphs
- Index(es):