Search All of the Math Forum:

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

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

 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

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

Date Subject Author
8/3/11 candide
8/3/11 Dan Hoey
8/3/11 candide