CODEWITHSUNDEEP
graph-theorybipartite
esraaelsayed
esraaelsayed

Reputation: 39

bipartite minimum edges

I looking for a simple algorithm getting the minimum weighted edge among the edges for a bipartite graph. I searched and I all could know it means the cover edge of a bipartite in other words if we have bipartite graph and each edge has a number weight how to get the smallest number among them

example

Upvotes: 3

Views: 3731

Answers (3)

dberm22
dberm22

Reputation: 3203

Even better than the Hungarian Algorithm as suggested in the other answers, is the Jonker-Volgenant (LAPJV) algorithm.

Take a look at this GitHub repository aptly named Bipartite Solver, which is basically a tutorial on how to implement LAPJV in code, complete with a runnable graphical sample.

It's crazy fast, able to do 1000 to 1000 in under a second.

Also included in the library is greedy search, which is even faster, but does not guarantee optimality.

The library also has some executables if you wish to try out the algorithms without having to build it from source.

Upvotes: 0

renqHIT
renqHIT

Reputation: 194

You need the Hungarian algorithm. Click here to get lecture notes.

Before processing, you should have a cost matrix, where each entry is the edge cost from node A to node B. The matching steps as follows:

  1. Substract the smallest entry in each row
  2. Substract the smallest entry in each column
  3. Draw lines through appropriate rows and columns, so that all the zero entries of the cost matrix are covered and the minimum numver of such lines is used
  4. Test for optimally: (1) if the minimum number of covering lines is n, an optimal assignment is possible and we are finished. (2) if the ninimum number of covering lines is less than n, an optimal assignment of zeros is not yet possible. GOTO step 5.
  5. Determine the smallest entry not covered by any line. Substract the entry from each uncovered row, and then add it to each covered column. Return to step 3.

The algorithm above is based on a mathematic therorem that

  • If a number is added to or substracted from all of the entries of any one row or column of a cost matrix, then an optimal assgnment for the resulting cost matrix is also an optimal assgnment for the original cost matrix.

Upvotes: 0

mmgp
mmgp

Reputation: 19241

The way this question is posed makes it very unclear. One of the interpretations I got from it was: "Given a weighted bipartite graph G, how do I obtain the minimum edge cover of G ?". If that is the case, then the Hungarian algorithm (see http://reference.wolfram.com/mathematica/ref/FindEdgeCover.html also) solves your problem.

Upvotes: 0

Related Questions