We are given a weighted complete bipartite graph G = (X; Y; X x Y ), where X = {

Question

We are given a weighted complete bipartite graph G = (X; Y; X x Y ), where X = {x1.....xn} and Y = {y1 ........ ym}, with n < m. By w(i,j) we denote the weight of edge (x i ; yj ). A cross-free matching M is a matching between X and Y in which no two edges "cross". More specically, if i < j and (x i ; y k ); (x j ; y l ) (belong to) M then k < l. The weight of a matching M is the sum of the weights of the edges in M . Give a dynamic programming algorithm that computes a perfect cross-free matching in G of minimum weight (perfect here means that each node in X is matched { some of the nodes in Y will remain unmatched). Analyze the space and time complexity of your solution

Explanation / Answer

Answer:

set = {}
i = input.length - 1
while i >= 1
if input[i] == input[i - 1]
    i--
else
    set << vertex i
    i -= 2
end
end
return set

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.