Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>What you are describing is known as the <a href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs" rel="nofollow noreferrer"> matching problem for bipartite graphs</a>. I suspect there is something (as yet unstated) about the problem which makes it difficult to solve. So far you really haven't placed any restriction on what edges can be used. Supposing that there are certain edges (not all) available, those "possible" edges form a graph, and the ones you decide to use form a maximum matching. Finding a maximum matching in a graph is a polynomial time algorithm, and it is particularly easy to code for the bipartite case.</p> <p>The title makes it sound as though circumstances might impose some circumstance so that "disjoint" edges might not be feasible ("least edge intersections"). Perhaps you want edge covering (or 1-cover), i.e. that every vertex belongs to at least one edge. Then, if the two "vertex" arrays are of different length, there will not be a "perfect matching", i.e. a matching that is also a cover. A classic result <a href="http://en.wikipedia.org/wiki/Marriage_theorem" rel="nofollow noreferrer"> Hall's Marriage Theorem</a> characterizes when there are perfect matchings in a bipartite graph. If the graph is regular (all vertices have equal degree), then <a href="http://en.wikipedia.org/wiki/Konig_theorem_%28graph_theory%29" rel="nofollow noreferrer"> König's Theorem</a> tells us there is perfect matching (and more).</p> <p><strong>Added:</strong></p> <p>It may be worth stating what the picture seems to say about the restrictions on choosing edges. Two sets of vertices have coordinates {(i,0) | i=1,..,N} and {(j,1) | j=1,..,N}. There are N available edges, line segments that connect (i,0) and (j,1) whenever y0[i] = y1[j]. Although the subject line says "least edge intersections", a solution is a maximum subset of these edges that admits no intersections, a largest <a href="http://en.wikipedia.org/wiki/Planar_straight_line_graph" rel="nofollow noreferrer"> planar straight-line graph</a> contained in a given <a href="http://en.wikipedia.org/wiki/Permutation_graph" rel="nofollow noreferrer"> permutation graph</a>.</p> <p>It is related to the 2-level crossing minimization problem considered here:</p> <p><a href="https://domino.mpi-inf.mpg.de/internet/reports.nsf/c125634c000710d0c12560400034f45a/4dc1ae56dd0efd5dc125645d002f8502/" rel="nofollow noreferrer">An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel</a></p> <p>"We suggest... removing the minimal number of edges such that the resulting graph is k-level planar... In this paper we address the case k = 2... [W]e address the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is NP-hard."</p> <p>The present problem imposes an equal number of points in the two vertex sets, the base graph is regular of degree 1, and no choice is allowed in the numbering or positioning of points. So it is not possible to conclude it is as hard as the one described in the above paper. However it does direct us to so-called "branch and bound" methods for the exact solution of such problems.</p> <p>Let's consider the "edges" of the original problem as "nodes" of a new graph where two nodes are adjacent iff the original edges intersect. [This is an example of an intersection graph.] The problem as restated is now to find <a href="http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29" rel="nofollow noreferrer"> a maximum independent set</a> of the new graph. The problems of that kind are in general NP-hard, but again we suspect the extent of the present problems may not be so general.</p> <p>One reason to suspect a polynomial time algorithm could exist is the availability of polynomial time approximation algorithms for maximum independent subsets of intersection graphs for finite collections of planar convex sets:</p> <p><a href="http://sma.epfl.ch/~moustafa/Research/Papers/indset.pdf" rel="nofollow noreferrer">Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa</a></p> <p>"In this paper, we present approximation algorithms for the independent-set problem on intersection graphs of line segments and convex objects in the plane."</p> <p>There is one further observation about the specialness of the present problem that seems to make it solvable in polynomial time. A <a href="http://en.wikipedia.org/wiki/Circle_graph" rel="nofollow noreferrer"> circle graph</a> is the intersection graph of line segments that can be drawn as chords of a circle. By a pertubation argument the straight-line edges of a permutation graph can be so drawn, without loss or introduction of intersections.</p> <p>Now the maximum independent set problem for circle graphs can be solved in polynomial time. The Wikipedia article linked above gives this reference: </p> <p><a href="http://dx.doi.org/10.1016%2Fj.ipl.2010.05.016" rel="nofollow noreferrer">Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters 116 (16): 630–634</a></p> <p>I also found this reference in Google Books: </p> <p><a href="http://books.google.com/books?id=fPAFulTD9jYC&amp;pg=PA129&amp;lpg=PA129&amp;dq=bipartite+permutation+graphs+matching+non-crossing&amp;source=bl&amp;ots=puSIIjK3Qv&amp;sig=Q5q7rCCkB6E5YoozgmvnzsqyF0k&amp;hl=en&amp;ei=we07Tf_DD8H38AbH0Y33Cg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=3&amp;sqi=2&amp;ved=0CCcQ6AEwAg#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">Valiente, Gabriel (2003), "A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs", Algorithms and computation: 14th Symposium, ISAAC 2003 Kyoto</a></p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm for Least Edge Intersections
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UShardmath
    1. UShardmath
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    1. CO`haven't placed any restriction on what edges can be used.` I'm sorry, could you elaborate?
      singulars
      1. PO
      1. USst0le
    2. COAlso the "edges" in the problem does not refer to graph edges, as they have an explicit geometric position. So, some isomorphism is missing here
      singulars
      1. PO
      1. USDr. belisarius
    3. COAs the problem is stated there are no geometric positions given, no data by which it might be determined whether two edges intersect in a geometric sense. That is the sort of "restriction on what edges can be used" that would make the problem nontrivial.
      singulars
      1. PO
      1. UShardmath
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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