Is this an NP complete problem?

formyfamilyandgoodfriend_at_yahoo.com.cn
Date: 12/02/03 

Date: Tue, 02 Dec 2003 21:07:22 GMT

Hi,

Could you give me some suggestions on this problem? Thanks for your
time and attention first.

The problem I am thinking is as follows:

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?

Finally thanks a lot for your time and attention once again.

Best regards,
Helen

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

Relevant Pages

  • Re: Is this an NP complete problem?
    ... # time and attention first. ... # Given an undirected graph. ... Gerhard J. Woeginger http://wwwhome.cs.utwente.nl/~woegingergj/ ...
    (comp.theory)
  • Re: Is this an NP complete problem?
    ... >Given an undirected graph. ... [that fails mail your article to, ... [ask your news administrator to fix the problems with your system. ...
    (comp.theory)