Help-Site Computer Manuals
Software
Hardware
Programming
Networking
  Algorithms & Data Structures   Programming Languages   Revision Control
  Protocols
  Cameras   Computers   Displays   Keyboards & Mice   Motherboards   Networking   Printers & Scanners   Storage
  Windows   Linux & Unix   Mac

Graph::Bipartite
Graph algorithms on bipartite graphs.

Graph::Bipartite - Graph algorithms on bipartite graphs.


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).

Programminig
Wy
Wy
yW
Wy
Programming
Wy
Wy
Wy
Wy