The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: [Graph algorithm] Does this problem have a name ?
Replies: 2   Last Post: Aug 3, 2011 4:39 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Dan Hoey

Posts: 172
Registered: 12/6/04
Re: [Graph algorithm] Does this problem have a name ?
Posted: Aug 3, 2011 3:16 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 8/3/11 1:30 PM, candide wrote:
> Consider the following question relative to graph theory :
>
>
> Let G a bipartite graph. To make the problem more concrete suppose G is
> the disjoint union of two sets, say I and S. Suppose
>
> *) I represents Individuals with name 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
> *) S represents Skills with name a,b, c, d, e, f, g, h.
>
> So, each individual has _some_ skills, for instance,
> -- individual 1 has skills b, d, g, and h,
> -- individual 2 has skills a, f, and h,
> -- etc.
>
>
> [in the example, datas are randomly given].
>
>
> We aim to build a team composed of the _minimum_ number of individuals
> from I in such a way that _every_ skill in S will be represented in the
> team, that is for each skill s in S, there exists a member of the team
> having the skill s.
>
> Does this problem have a name ? Does an efficient algorithm for solving
> it is known ?


You can transform this from a graph problem to a set problem by
providing as input the list of all the skill sets. The set problem is
called MINIMUM COVER in Garey and Johnson. It is NP-complete even if
each individual has exactly three skills, and even if we only want to
know whether there is an exact cover (a cover in which no skill is
duplicated).

Dan



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.