I am solving a problem, which has a weighted complete bipartite graph(X,Y,XxY), where X has n nodes and Y has m nodes and n is less than m. I want to have a perfect cross free matching graph, such that no two edges cross while matching set X to set Y and all the nodes in X are taken at the end.The sum of weights of the resulting graph should be minimal, I need to devise a dynammic programming algorithm. This is how I thought of it:
nodes in X and Y are arranged x0, xi can have a horizontal edge to Y0,Yi and so on, but Y has more nodes than X. For every node in X (i) I consider two options either horizontal neighbor which is j in set Y, or diagonal neighbors (i, j-1), (i,j+1) and choose the edge which minimizes the cost.and I keep track of the nodes in X and Y that are already taken.time complexity O(nm)
Is there a better way I can implement this. Any help is appreciated. This is a question I got in my midterm but I left it in choice.
Let w(x, y) be edge weight between nodes x in X and y in Y, and let M(i, j) be solution (minimum cross free matching graph) for vertices {x_0, x_1, ..., x_i} subset X and {y_0, y_1, ..., y_j} subset Y, where i < |X| and j < |Y|.
E.g. M(0, j) = min( w(x_0, y_a) ) for 0 <= a <= j. M(i, i-1) = infinity since there is no matching when 'right' set is smaller.
For i, j there are two possibilities: x_i is connected to y_j or not. Because of that recursion holds:
M(i, j) = min( w(i,j) + M(i-1, j-1), M(i, j-1) )