Re: Is this an NP complete problem?

"Lucas B. Kruijswijk" <[EMAIL PROTECTED]> writes:

> > Given an undirected graph. Every edge in this graph will be in a
> > specific color. Now I want to find a subset of edges that contains the
> > least kinds of colors.
> >
> > Is it an NP complete problem?
> You maybe mean a connected graph with the least number of colours?

If this is the case, then it is NP complete as SETCOVERING can be
reduced to it.

/Bjarke

[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <[EMAIL PROTECTED]>, and ]
[ ask your news administrator to fix the problems with your system. ]