StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Define a new undirected graph <code>G'</code> from <code>G</code> as follows.</p> <ol> <li><code>G'</code> has a node <code>(A, B)</code> with weight <code>w</code> for each directed edge <code>(A, B)</code> with weight <code>w</code> in <code>G</code></li> <li><code>G'</code> has undirected edge <code>((A, B),(B, C))</code> if (A, B) and (B, C) are both directed edges in G</li> </ol> <p><a href="http://en.wikipedia.org/wiki/Line_graph#Line_digraphs">http://en.wikipedia.org/wiki/Line_graph#Line_digraphs</a></p> <p>Now find a maximal (weighted) independent vertex set in <code>G'</code>.</p> <p><a href="http://en.wikipedia.org/wiki/Vertex_independent_set">http://en.wikipedia.org/wiki/Vertex_independent_set</a></p> <h2>Edit: stuff after this point only works if all of the edge weights are the same - when the edge weights have different values its a more difficult problem (google "maximum weight independent vertex set" for possible algorithms)</h2> <p>Typically this would be an NP-hard problem. However, <code>G'</code> is a bipartite graph -- it contains only even cycles. Finding the maximal (weighted) independent vertex set in a bipartite graph is <em>not</em> NP-hard.</p> <p>The algorithm you will run on <code>G'</code> is as follows.</p> <ol> <li>Find the connected components of <code>G'</code>, say <code>H_1, H_2, ..., H_k</code></li> <li>For each <code>H_i</code> do a 2-coloring (say red and blue) of the nodes. The cookbook approach here is to do a depth-first search on <code>H_i</code> alternating colors. A simple approach would be to color each vertex in <code>H_i</code> based on whether the corresponding edge in <code>G</code> goes from <code>U</code> to <code>V</code> (red) or from <code>V</code> to <code>U</code> (blue).</li> <li>The two options for which nodes to select from <code>H_i</code> are either all the red nodes or all the blue nodes. Choose the colored node set with higher weight. For example, the red node set has weight equal to <code>H_i.nodes.where(node => node.color == red).sum(node => node.w)</code>. Call the higher-weight node set <code>N_i</code>.</li> <li>Your maximal weighted independent vertex set is now <code>union(N_1, N_2, ..., N_k)</code>.</li> </ol> <p>Since each vertex in <code>G'</code> corresponds to one of the directed edges in <code>G</code>, you have your maximal DirectionalMatching.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload