Is there a palpable implementation for solving the minimum cost maximum matching for general graphs?

Правка en1, от mouse_wireless, 2024-10-25 21:32:09

So I know that for maximum matching in general graphs (without the cost part), we have Edmond's blossom algorithm, for which there are some nice tutorials, and I've seen a number of nifty, digestible implementations.

The wikipedia article says that the Blossom Algorithm can be used to find the minimum cost maxmimum matching as well, but the only reference I found to this online was this paper on Blossom V, which I at least find very difficult to read; and while they do provide a C++ implementation, it has thousands of lines between all the different files.

Is there a more "palpable" implementation for solving this problem? Something more fitting for programming competitions?

Теги matching, graphs, cost, edmond

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский mouse_wireless 2024-10-25 21:32:09 994 Initial revision (published)