Minimal vertex cover for bipartite graphs
Computes a minimum vertex cover of a bipartite graph. Internally, this implementation uses the Hopcroft-Karp algorithm and Konig's theorem to compute the minimal vertex cover of a bipartite graph in O(sqrt(V) * E) time. This code works in both node.js and in a modern browser via browserify.
var findCover = require"bipartite-vertex-cover"var cover = findCover4 40 11 01 11 22 13 23 3// Cover = [ [3, 1],  ]
npm install bipartite-vertex-cover
Finds a minimal vertex cover for a bipartite graph.
nis the number of vertices in the left component
mis the number of vertices in the right component
edgesis a list of edges from the left component connecting to the right component represented by pairs of integers between 0 and n-1,m-1 respectively
Returns A pair of lists representing the vertices in the left component and the right component respectively which are in the cover.
(c) 2014 Mikola Lysenko. MIT License