CODEWITHSUNDEEP
graphgraph-algorithm
Boris
Boris

Reputation: 1

Algorithm for solving a shortest edges problem?

Here is the problem: For a graph of several nodes, each node could only connect to one of the other nodes. How to minimize the total edges of this graph? Fig.1Fig.2

As the above, Fig.2 has shorter length than that of Fig.1. Is there an algorithm to calculate the shortest length of the total edges?

Upvotes: 0

Views: 36

Answers (1)

collapsar
collapsar

Reputation: 17268

The problem is called 'minimum weight perfect matching'. Kolmogorov, V. - Blossom V: A new implementation of a minimum cost perfect matching algorithm presents an efficient algorithm. The C++ implementation of the algorithm in the paper is available (retrieved from here; the link given in the paper itself is no longer active).

A cursory Google search suggested that various graph processing libraries ( like LEDA ) include an algorithm for solving your problem in their toolbox.

Caveat

I have not tested the implementation of the cited paper and do not know about the legal status of using it.

Upvotes: 1

Related Questions