most recent 30 from http://mathoverflow.net 2013-05-25T20:19:33Z http://mathoverflow.net/feeds/question/41376 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41376/digraphdag-partitioning-to-subgraphs krolya 2010-10-07T07:38:00Z 2010-10-09T16:06:44Z

<p>Hello </p> <p>Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes.</p> <p>(Note: <strong>Approximately</strong> means that each subgraph contains $\lceil \sqrt{n}\rceil$ or $\lfloor \sqrt{n} \rfloor$ nodes and covers $\lceil \sqrt{s}\rceil$ or $\lfloor \sqrt{s} \rfloor$ sourses of the original graph. All <strong>sources</strong> of the original graph have to be covered by some subgraph, so there has to be $\lceil \sqrt{s}\rceil$ or $\lfloor \sqrt{s} \rfloor$ subgraphs.)</p> <p>Let's define the <strong>height</strong> of the DAG to be the maximum path length from some source to some sink.</p> <p>The subgraphs have following requirements:</p> <ol> <li>We require that all subgraphs generated will have the same height( max length of longest path)</li> <li>Nodes of each subgraph should be reachable from the sources within that subgraph, using nodes of that subgraph as intermediate nodes.</li> <li>Moreover, the intersection of each pair of node sets (of subgraphs) must be empty.</li> </ol> <p>In the following picture, you can see an example of a right partition (assume that each edge in the graph is directed upwards).</p> <p><a href="http://i.imgur.com/PSaBI.png" rel="nofollow">http://i.imgur.com/PSaBI.png</a></p> <p>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.</p> <p>Do you have idea for algorithm?</p> <p>Thank you very much </p>