Re: What is general term for this problem?

From: Kenneth Downs <firstinit.lastname_at_lastnameplusfam.net>
Date: Thu, 16 Sep 2004 19:00:26 -0400
Message-ID: <bu5dic.99q.ln@mercury.downsfam.net>

Jan Hidders wrote:

> On Thu, 16 Sep 2004 12:34:23 -0400, Kenneth Downs wrote:

>> 

>
> That would be '(maximum) bipartite matching' of which the 'marriage
> problem' is probably the simplest example. These are special cases of
> 'constraint satisfaction problems' but where these are in general NP-hard
> the bipartite matching problems can often be solved in polynomial time.
> The usual way of showing this is by translating it to the problem of
> finding the maximal flow in a certain network and solving it with the
> Ford-Fulkerson method.
>
>
> -- Jan Hidders

Wonderful, thanks. I also found some very interesting stuff at

http://www.planetmath.org/encyclopedia/bipartitegraph.html

-- 
Kenneth Downs
Use first initial plus last name at last name plus literal "fam.net" to
email me

Received on Thu Sep 16 2004 - 18:00:26 CDT