f

#### Is this problem an NP - complete problem?

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

 0
formyfamilyandgoodfr
12/2/2003 10:53:22 AM
comp.graphics 550 articles. 1 followers. LawsonE (253) is leader.

0 Replies
580 Views

Similar Articles

[PageSpeed] 4

Similar Artilces:

problems problems problems
(The short(?) summary) I've got an Access MDB file and a DAO connect with it.. Problem 1 of 2 The below gives me a runtime error 91 Object variable or With block variable not set. I've got the db stuff after the form.show (to make sure all the objects on the form are loaded before attempting to utilize/manipulate them) But it doesn't like it when I use the data object in the form load anyway for some reason.. pffft. Private Sub Form_Load() frmTest1Project.Show datGallery.Recordset.MoveLast datGallery.Recordset.MoveFirst Call LockTextBoxes(frmTest...

NP problem and co-NP problem
Hello, please let me post my last question again because the old name seems to make problems with other threads. Why is it true that NP = co-NP if there is an NP-complete language L whose complement is in NP, too? My textbook argues as follows (cL denotes the complement of L): Because every NP language S is polynomial-time reducible to L, i.e. S<L if follows that cS is polynomial-time reducible to cL, i.e. cS<cL... I don't understand this up to here. Why does cS<cL follow? Could anybody help me? Another question is what happens if there is an NP-complete language L which is is...

is this kind of problem a NP or non-NP problem?
Hello all, I am just learning computation theory and encounter the following situation that I donot know what to do. when we consider the complexity of an algorithm, we always refer to its input. For example, for an algorithm with input size n, the complexity is O(n^2). Here comes my question. the current discussion of (worst case) complexity is with respect to the input size n, and we express the complexity as a function of n using big O notation. Therefore, the same algorithm, but with respect to different view of input size, may have different complexities. What I means is 1. given a pro...

Problems problems....
I've got Fujitsu MAN3184MP and Adaptec 29160 scsi card. Sometimes i have this message "A disk read error occured" , sometimes even bios does not recognize it, sometimes it does but the boot sequence does not start it seems that motherboard bios has problems with it ( so it seems to me, i could be wrong about that assumption) . Then i reset and it all works perfectly. I've noticed a speed degradation in Win XP lately. I'm angry :)) I have LVD/SE terminator, and i think 68pin cable ( not sure about that ). Hope i gave you enough info to try and help. Thanx! -- -...

Problem with a problem
Hello, take a grammar G with alphabet {0,1} such that (the word problem for) the language L_G={w in (0+1)*|w\in L(G)} is very complex, say in PSPACE or some higher complexity class. Now consider an "easy" problem EASY like: "Is an element of L_G in L_G?". Well, this seems to be fairly easy because the answer is "yes" in any case. Hence the problem should be of small complexity. But if one models such a decision problem one has to construct a language L with alphabet A such that the word problem for L reflects exactly the decision problem which one is interested...

Problems in NP^(NP^NP) that are not in NP^NP?
Hello all, Does anyone know of a problem that is in NP^(NP^NP) that is not known to be in NP^NP? (This could not be proven short of proving P != NP, since if P = NP the two classes mentioned are both equal to P.) I know from Sipser's textbook that NONMIN_FORMULA is in NP^NP but probably not in NP; but I couldn't come up with a problem that is in NP^(NP^NP) that's probably not in NP^NP. Also, if anyone knows of such a problem, is there a general method to find such problems for any number of iterations of adding NP oracle machines to the class? In other words...is there a way ...

Re: How many files can you have in a VMS directory without performance problems? performance problems? performance problems? problems? performance problems? performance problems? problems? perfo
First, does anyone know why Info-VAX goes nuts on subjects from time to time? (Or is the trouble elsewhere?) From: JF Mezei <jfmezei.spamnot@teksavvy.com> > DELETE Z*.*;* > DELETE Y*.*;* > ... > DELETE A*.*;* > > (followed by the numbers). This scheme may be a bit obsolete. See: http://h71000.www7.hp.com/doc/731FINAL/4506/4506pro_014.html#index_x_890 I quote: [...] 5.2.3.1.2 Extended Character Set In addition, OpenVMS V7.2 on Alpha systems and ODS-5 disks includes support for the use of file names, and subdirectory and root subdirectory names, tha...

Re: How many files can you have in a VMS directory without performance problems? performance problems? performance problems? problems? performance problems? performance problems? problems? perfo #2
On 8/17/05, Mark Berryman <mark@theberrymans.com> wrote: > Steven M. Schweda wrote: > > First, does anyone know why Info-VAX goes nuts on subjects from time > > to time? (Or is the trouble elsewhere?) >=20 > Elsewhere. Info-VAX does not rewrite the subject. >=20 > Mark Berryman > Info-VAX admin >=20 I thought it was reacting to poster sanity bugchecks. : ^ ) WWWebb --=20 NOTE: This email address is only used for noncommerical VMS-related correspondence. All unsolicited commercial email will be deemed to be a request for services pursuant to the t...

Is this a BIOS problem, a kernel problem or a user problem :-)
Hi all, I have a Dual Core P4, which dmesg reports as (CPU0 and) CPU1: Intel(R) Pentium(R) 5 CPU 2.66GHz stepping 07 Unfortunately, it is also reporting CPU: Hyper-Threading is disabled I went through the BIOS (AMI dated 2005) and saw no option to enable HT. uname -a reports Linux hwa3 2.6.17-10-generic #2 SMP Fri Oct 13 18:45:35 UTC 2006 i686 GNU/Linux so clearly the BIOS and the kernel see the processor as dual core. Is there a utility to do this (enable hyperthreading)? Am I going to have to recompile the kernel? Is there a set of Intel dual core CPU's which does not have H...

CUPS problem? or network problem? or printer problem?
Trying to configure CUPS to print to an HP LaserJet 5si over the network. Here is the relevant error_log stuff: I [17/Nov/2003:14:19:03 -0500] Job 14 queued on 'ptr' by 'wm'. I [17/Nov/2003:14:19:03 -0500] Started filter /usr/lib/cups/filter/texttops (PID 12120) for job 14. I [17/Nov/2003:14:19:03 -0500] Started filter /usr/lib/cups/filter/pstops (PID 1 2121) for job 14. I [17/Nov/2003:14:19:03 -0500] Started filter /usr/lib/cups/filter/pstoraster (P ID 12122) for job 14. I [17/Nov/2003:14:19:03 -0500] Started filter /usr/lib/cups/filter/rastertoprint er (PID 1...

Lan problems problems
Hi can anyone please offer a suggestion to a LAN Problem i have. Recently my server computer on a 3 access point lan network has been dropping out after about 10 minutes. if i disconnect the power from the ethernet switch/hub and reconnect after 5 minutes, then it works again for a short time. there is no disconnection from the other servers. I have,..... 1.reformatted and rebuilt windows xp pro. 2.tested the switch/hub on another computer, seems ok 3. tested the lan cables. 4. tested the lan access points. yet still i have the trouble. any suggestions would be welcomed. D.Thomas Di...

problem with a minimazition problem.
Hello, I have a problem with a minimazition problem: Let my aim is to find x and a where f(x,a) is minimized with the constraint g(x,a)=0. Here "a" is parameter. It is known that for some values of x and a, function g does not have real roots of x. In matlab, I use fmincon function to solve this minimazition problem with "interior-point" algorithm. However, even in situations where g doesnt have real x roots , somehow Fmincon finds solution. I want to determine which solutions have real roots which are not. How can I do that? To which criterian do I have to...

Lan problems problems
Hi can anyone please offer a suggestion to a LAN Problem i have. Recently my server computer on a 3 access point lan network has been dropping out after about 10 minutes. if i disconnect the power from the ethernet switch/hub and reconnect after 5 minutes, then it works again for a short time. there is no disconnection from the other servers. I have,..... 1.reformatted and rebuilt windows xp pro. 2.tested the switch/hub on another computer, seems ok 3. tested the lan cables. 4. tested the lan access points. yet still i have the trouble. any suggestions would be welcomed. D.Thomas Di...

A simple problem, but a problem ...
Hello, can anyone solve the following problem ? It looks quite simple to me, but I can't get it right. The advice suggests the following: mr(yes). mr(no). mrs(yes). mrs(no). marcel(yes). marcel(no). jacqu(yes). jacqu(no). grandpa(yes). grandpa(no). but how can I use this to solve the problem ? thanx a lot Maxx Problem: If Mr. Johnson goes, his wife goes too. At least one of the children, Marcel or Jacqueline, goes too. If Marcel goes, grandpa goes too. If Mrs. Johnson goes, grandpa stays at home. If Jacqueline goes, Mr. Johnson and Marcel go too. Write a prolog program, which det...

Linux, ISE 7.1, problems, problems, problems ....
ok, ok we've beaten this subject to death already .... I just had this really radical and crazy idea: XILINX, how about a BETA program ? I mean one before you burn the CDs and make a product announcement and we are stuck with a useless plastic disc. If I look at all the issues that people are having with 7.1, they are all so trivial and easy to to solve (include a few libs, distribute a statically linked setup program, etc.). I'm sure a few of us with subscription would volunteer to test drive a pre-release version of your s/w. - I know I would. Wouldn't that be much nicer t...

Web resources about - Is this problem an NP - complete problem? - comp.graphics

Complete game - Wikipedia, the free encyclopedia
In the early 20th century, it was common for most good Major League Baseball (MLB) pitchers to pitch a complete game almost every start. Pitchers ...

Launch A Complete Facebook Marketing Campaign
The early bird deadline for Mediabistro's Facebook Marketing Boot Camp is Wednesday, March 28.

India claim thrilling last-ball win over Australia to complete series whitewash
Shane Watson silenced his doubters and all but booked himself a ticket to the World T20 in March with a sparkling century, but it mattered little ...

India claim thrilling last-ball win over Australia to complete series whitewash
Shane Watson silenced his doubters and all but booked himself a ticket to the World T20 in March with sparkling century, but it mattered little ...

Shane Watson makes ton but India beats Australia to complete T20 series sweep
India completes a clean sweet of the three-match T20 series against Australia with a last-ball win at the SCG.

A complete collection of Donald Trump’s Twitter insults
Donald Trump has been insulting people on Twitter since long before he was the leading Republican candidate for president of the United States ...

BT's acquisition of EE is complete
For BT and EE, the moment has finally arrived. All of the relevant regulators have given their approval, allowing BT to acquire the UK's largest ...

SAG Awards 2016 Winners: The Complete List
E! Online SAG Awards 2016 Winners: The Complete List E! Online Tonight is the night for the 22nd Annual Screen Actors Guild Awards! One of ...

SAG Awards 2016: The Complete Winners List
SAG Awards 2016: The Complete Winners List

Resources last updated: 2/1/2016 7:53:27 AM