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