bipartite graph and dynamic programming

Question

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.

Ante · Accepted Answer · 2014-03-06 11:00:55Z

0

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) )

answered Mar 6, 2014 at 11:00

Ante

5,4686 gold badges26 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Abhijit Sarkar Over a year ago

I don't see how this algorithm enforces the cross-free constraint.

Ante Over a year ago

That is due every matching edge is added with w(i,j) + M(i-1, j-1) part, which connects last elements. So adding (every) new edge is 'safe'.

Abhijit Sarkar Over a year ago

I think what you're saying is only true if j >= i which is not mentioned by the algorithm. Or am I missing something?

Ante Over a year ago

That is covered by intializing M(0, j) = inf, or if you want M(i, j) = inf for i < j. Second initialization is evaluated by recursion and first initialization.

Collectives™ on Stack Overflow

bipartite graph and dynamic programming

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related