bipartite-vertex-cover

    1.0.0 • Public • Published

    bipartite-vertex-cover

    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.

    Example

    var findCover = require("bipartite-vertex-cover")
     
    var cover = findCover(4, 4, [
        [0, 1],
        [1, 0],
        [1, 1],
        [1, 2],
        [2, 1],
        [3, 2],
        [3, 3]
        ])
     
    // Cover = [ [3, 1], [1] ]

    Install

    npm install bipartite-vertex-cover
    

    require("bipartite-vertex-cover")(n, m, edges)

    Finds a minimal vertex cover for a bipartite graph.

    • n is the number of vertices in the left component
    • m is the number of vertices in the right component
    • edges is 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.

    Credits

    (c) 2014 Mikola Lysenko. MIT License

    Install

    npm i bipartite-vertex-cover

    DownloadsWeekly Downloads

    13

    Version

    1.0.0

    License

    MIT

    Last publish

    Collaborators

    • mikolalysenko