Talk:Dominator (graph theory)

From Wikipedia, the free encyclopedia

The definition of immediate dominator is tautological, it uses concept of immediate dominance without explaining what it is. If I understood correctly, immediate dominator would be defined as something like:

"Node d immediately dominates node n, if it is its dominator, and there exists no dominator of n that isn't also dominator of d"

Is that correct? Mathrick 11:39, 22 Apr 2005 (UTC)

I think your definition is correct, but I added a definition in terms of strict dominators, because this seems a little easier to understand. The original "definition" was quite silly. Deco 16:55, 22 Apr 2005 (UTC)

[edit] Wrong

Removing this:

<actually this algorithm is wrong, it can't handle circles, e.g , 4 is precedors of 5, and 5 point to 6, 6 point to 7 and 8, 7 point back to 5, 8 also point back to 5, then the algorithm will never put 4 in the dominators of 5, because 7,8 can appear before 5 in the path, so the intersection can't add 4 into it, but for 7,8 Dom(7), Dom(8) all depend on Dom(6) which depends on Dom(5), which never has 4 in it, so Dom(7),Dom(8) will never have 4 in it, well, you got the idea>

because it appears to be someone's confused opinion. It would be true if Dom(n) was initialized to {}, but it is initialized to the set of all nodes. Aij 15:47, 24 October 2007 (UTC)