<p>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.</p>

<p>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.)</p>

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

CC BY-SA 3.0
2014-04-09T18:09:20.367Z
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
CC BY-SA 3.0
2014-04-10T04:25:27.150Z
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
CC BY-SA 3.0
2014-04-09T11:49:48.357Z
2014-04-09T18:18:55.707Z
2014-04-09T18:18:55.707Z
Darcy
<p>I recently learnt about the concept of <a href="http://en.wikipedia.org/wiki/Dominator_(graph_theory)" rel="nofollow">dominator trees</a> and was fascinated by it.</p>

<p>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?</p>

<p>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 &gt; 1)</p>

<p>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 <a href="http://google-engtools.blogspot.com/2011/08/build-in-cloud-how-build-system-works.html" rel="nofollow">build targets</a>)</p>

CC BY-SA 3.0
2013-05-09T13:51:45.087Z
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
<graph-theory><graph-algorithms><ds.data-structures><directed-acyclic-graph>
Multiple-sources dominator trees: compact representation and fast algorithm?
jkff
# Multiple-sources dominator trees: compact representation and fast algorithm?

(Asked by: username_0 on 2013-05-04)

I recently learnt about the concept of [dominator trees](http://en.wikipedia.org/wiki/Dominator_(graph_theory)) 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](http://google-engtools.blogspot.com/2011/08/build-in-cloud-how-build-system-works.html))

**Tags:** graph-theory, graph-algorithms, ds.data-structures, directed-acyclic-graph

> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2014-04-09. Score: 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.

> **Comments:**
> **username_3**: What does "at least $o(n^2)$" mean? $o(-)$ gives upper bounds so, in effect, you're saying "at least less than $n^2$".  
> **username_2**: 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.  

---

