Maximum Bipartite Matching

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
Liglogthepanda
Forum Newbie
Posts: 1
Joined: Wed Jul 09, 2008 3:25 pm

Maximum Bipartite Matching

Post by Liglogthepanda »

A question for those familiar with graph theory or the matching type of algorithms:

So I have a bipartite graph and I want to perform a maximum matching operation on it. If I call the 'left hand side' "items" and the 'right hand side' "bins", I want to input which items can fit in which bins, and be output with "Item A goes into Bin X, Item B in Bin Y", etc.

Obviously I've simplified this. But the PHP will need to include Dijkstra's algorithm somewhere (which I can understand with pen-and-paper but not in code).

I can't think of any way to do this ... at all. Help!
Post Reply