I am working on the following problem-

"Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching."

Please note that I like to search over all possible matching (that includes maximum matching and other matchings as well). As per my knowledge, Hungarian algorithm searches over all possible maximum matching (and not among all matching). Please let me know if I can use the Hungarian algorithm to solve this problem.

  • $\begingroup$ Welcome to Computer Science! Are weights allowed to be negative? If they are nonnegative, then the empty matching has the minimum weight. If empty matching is not allowed, then just compare all matchings that contains one edge. Please clarify in the question. $\endgroup$ – John L. Nov 5 '18 at 4:55

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.