XPost: comp.graphics.algorithms, comp.theory, sci.math   
   XPost: sci.op-research   
   From: bjarke_ng@skjernaa.dk   
      
   "Lucas B. Kruijswijk"  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 , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)