Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I recently learnt about the concept of dominator trees and was fascinated by it.

I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in the graph as sources: can all-sources dominators be represented more compactly than in O(n^2) space and computed more efficiently than running the classic dominator tree algorithm from every vertex?

I tried searching for keywords like "multiple sources dominators" etc, but only found about "multiple-vertex dominators", which are a different thing (dominating sets of size > 1)

Does any of this become simpler if the graph is acyclic? (in fact, I work at Google and I think it'd be fun to apply this to the huge dependency graph of Google's build targets)

share|improve this question
    
I like this question! Intuitively there should be quite a lot of sharing, at least for the dag case. I have, however, a perhaps stupid question: Why would it help to know the dominators of a target in a build system? –  Radu GRIGore May 9 '13 at 13:51

1 Answer 1

I think it's really hard to do that. First of all, for one source dominator tree, there are several dominator points for a vertex. If we want to use "Lengauer-Tarjan algorithm", we can't avoid using tree structure. But how can we save a tree with less than $o(n)$ space? It means that for $n$ source dominator tree, we have to use at least $o(n^2)$ space unless we create a new structure which can represent dominator's information more effective.

For a dag, I remember there is a another algorithm to find whether two vertices share the same dominator for one source. Maybe it will help, you may search uva12671 for more information. (Actually, I am thinking a developing problem about this recently.)

Finally, I am also fascinated by it. If anybody has a new idea, please contact me anytime.

share|improve this answer
    
What does "at least $o(n^2)$" mean? $o(-)$ gives upper bounds so, in effect, you're saying "at least less than $n^2$". –  David Richerby Apr 9 at 18:09
    
I'm sorry.It's my fault.I used this from careless .I mean that in the worst case ,we have to use n^2 space. –  Darcy Apr 10 at 4:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.