Hello
Given a DAG with [TEX]$|V| = n$[/TEX] and has [TEX]$s$[/TEX] sources, we have to present subgraphs such that each subgraph has approximately [TEX]$k_1=\sqrt{s}$[/TEX] sources and approximately [TEX]$k_2=\sqrt{n}$[/TEX] nodes.
(Note: **Approximately** means that each subgraph contains[TEX] \lceil \sqrt{n}\rceil[/TEX] or [TEX] \lfloor \sqrt{n} \rfloor[/TEX] nodes and covers [TEX] \lceil \sqrt{s}\rceil[/TEX] or
[TEX]\lfloor \sqrt{s} \rfloor[/TEX] sourses of the original graph. All **sources** of the original graph have to be covered by some subgraph, so there has to be [TEX]\lceil \sqrt{s}\rceil[/TEX] or [TEX] \lfloor \sqrt{s} \rfloor[/TEX] subgraphs.)
Let's define the **height** of the DAG to be the maximum path length from some source to some sink.
We require that all subgraphs generated will have the same height.
Moreover, the intersection of each pair of node sets (of subgraphs) must be empty.
In the following picture, you can see an example of a right partition (assume that each edge in the graph is directed upwards).
[IMG]http://i.imgur.com/PSaBI.png[/IMG]
There are 36 nodes and 8 sources [#10,11,12,13,20,21,22,23] in the example. So each subgraph should have 6 nodes and 2 or 3 sources.
Do you have idea for algorithm?
Thank you very much