NAME

Graph::Bipartite - Graph algorithms on bipartite graphs.

SYNOPSIS

  use Graph::Bipartite;
  $g = Graph::Bipartite->new( 5, 4 ); 
  $g->insert_edge( 3, 5 );
  $g->insert_edge( 2, 7 );
  %h = $g->maximum_matching();

DESCRIPTION

This algorithm computes the maximum matching of a bipartite unweighted and undirected graph in worst case running time O( sqrt(|V|) * |E| ).

The constructor takes as first argument the number of vertices of the first partition V1, as second argument the number of vertices of the second partition V2. For nodes of the first partition the valid range is [0..|V1|-1], for nodes of the second partition it is [|V1|..|V1|+|V2|-1].

The function maximum_matching() returns a maximum matching as a hash where the keys represents the vertices of V1 and the value of each key an edge to a vertex in V2 being in the matching.

AUTHOR

Daniel Etzold, detzold@gmx.de

SEE ALSO

perl(1).