bipartite-matching
Finds a maximum bipartite matching in an unweighted graph. The current implementation uses the Hopcroft-Karp algorithm and runs in O(sqrt(V) * E + V) time. Works in both node.js and in a browser.
Example
var findMatching = console
Install
npm install bipartite-matching
require("bipartite-matching")(n, m, edges)
Computes a bipartite matching for the graph
n
is the number of vertices in the first componentm
is the number of vertices in the second componentedges
is the list of edges, represented by pairs of integers between 0 and n-1,m-1 respectively.
Returns A list of edges representing the matching
Credits
(c) 2014 Mikola Lysenko. MIT License