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_at_mercury.downsfam.net>
>
> 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
Date: Thu, 16 Sep 2004 19:00:26 -0400
Message-ID: <bu5dic.99q.ln_at_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 meReceived on Fri Sep 17 2004 - 01:00:26 CEST