I'm trying to find pairs in a complete, weighted graph, similar to the one below (weights not shown).
For each possible pair there is a weight and I would like to find pairs for including all vertices, maximizing the weight of those pairs.
Many of the algorithms for finding maximum matchings are only concerned with finding them in bipartite graphs (e.g. Hungarian algorithm). In this case the graph is not bipartite. The only algorithm I found that seems to fit the problem here is Edmond's Blossom algorithm and it's (revised?) Blossom V variant.
As far as I understand the complexity of Blossom is polynomial ($n^3$) and so with bigger graphs complexity increases quickly. I currently don't expect more than 100 vertices which should be manageable unless the $n$ in $n^3$ concerns the number of edges in the graph. In this case I might need to find a way to make the graph less dense.
My questions are:
- Is Blossom/Blossom V the only algorithm that should be considered for this problem or did I miss any other contenders while digging into this?
- Do you know if in these kinds of algorithms $n$ usually refers to the number of vertices or edges?
- Since even with Blossom this might be computationally intensive I was wondering if someone can think of some smart steps to simplify the problem, maybe turning it into another problem that could be easier to solve.