2
$\begingroup$

Say you have a graph consisting of $k$ red nodes and $k$ blue nodes in Euclidean $2$-d space. There is an edge between every red-blue pair, and edge weights are distances. Our goal is to find the min-weight matching.

The Hungarian algorithm solves the more general case where the edge weights are arbitrary. Is there a more efficient approach that takes advantage of the Euclidean aspect?

$\endgroup$

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.