0
$\begingroup$

For a robot vision problem, I'm matching observations to known robot locations. After searching this site, I have figured out that I need to find the maximum edge set of a bipartite graph (i.e., the Hungarian Maximum Matching Algorithm; however, in my case, there are many possible maximum independent edge sets (consider a square with four vertexes and four edges, which has two maximum independent edge sets).

I want to find the one with the smallest sum of edge weights (which are distances squared). How should I go about this? How can I use the aforementioned algorithm to find ALL maximum independent edge sets?

$\endgroup$
0
$\begingroup$

Found it. "Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs" by Takeaki Uno.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.