Maximum bipartite matchine problem can be converted to the maximum flow problem and it can be solved by Edmonds-Karp algorithm in O(VE)<=O(V^3). But there can be bounded problem, when the nodes on each side (n1, n2, ..., nn on the left side and m1, m2, ..., mn on the right side, the number of nodes on each side are equal) are ordered and node ni from the left side can be matched with only mj+1, mj+2, ..., mj+k neighbouring nodes only. It is suggested that maximum bipartite matchine can be found in O(V*logV) time (that is clearly better than the worst case O(V^3) in the general problem). what kind of problem is this and are there special algorithms for this?

logn factor in the suggested estimation hints that this problem can be reduced to the sorting problem? So, somehow all the pairs can be formed (but that can be n^2 in the general case?), each pair can be assigned some value and then top n pairs can be selected?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.