Is this an NP complete problem?

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

Date: Sat, 13 Dec 2003 01:52:58 GMT

Dear Sir/Madam,

Given an undirected graph, every edge in it will be in a specific
color. For example, there are 4 lines in the graph. Two lines are red.
One line is yellow. Another line is blue. Then there are totally 3
kinds of colors in this graph. I further assume there are n cut sets
in the graph. In one cut set, the lines are either red or yellow. So
there are 2 kinds of color in this cut set.

With the definition stated above, my objective is to find a cut set
that contains the least kinds of colors. I am wondering if this
problem is an NP complete problem.

Thanks a lot for your attention and look forward to your advice!

Best regards,
Helen

Relevant Pages

  • Re: Is this an NP complete problem?
    ... Best regards, ... A graph G is a pair, where V is a set of vertexes, ... > We must all be aware that new maths is being created far faster than any one ... In one cut set, the lines are either red or yellow. ...
    (comp.theory)
  • Re: Is this an NP complete problem?
    ... the art of maths is to write it so that those of all specialisatons ... A graph G is a pair, where V is a set of vertexes, ... In one cut set, the lines are either red or yellow. ...
    (comp.theory)
  • Re: Getting values from the plots
    ... have a look at the rangefrompoint method, ... Regards, ... > I need to create a graph control that allows me to plot the graph from an ... > mouse up and mouse down to get the cursor positions on the graph. ...
    (microsoft.public.office.developer.web.components)
  • Re: Render url stream
    ... I cannot check any graph ... > event) on the calling thread until it got the first frame. ... > Best regards, ...
    (microsoft.public.win32.programmer.directx.video)
  • Re: graphs showing unwanted zero values
    ... > Select Chart, goto menu: ... >> I have tried every possible combination when cliking the graph, ... >> Zadig Galbaras ...
    (microsoft.public.excel.misc)