Formulate the corresponding coffee-machine decision problem

Assignment Help Theory of Computation

Reference no: EM13470696

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that does have a coffee machine. (For any two meeting rooms, the architect has told us whether or not they are close enough.) Our problem is to determine among all the meeting rooms of any university campus, which ones should have coffee machines so that we use as few coffee machines as possible. Specify this problem as an optimization problem on a graph. Formulate the corresponding Coffee-machine Decision Problem (abbreviated Coffee). Prove that the Coffee Machine Decision Problem is NP-complete.

Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.

Reference no: EM13470696

Questions Cloud

Test hypothesis that exercises enhanced peripheral vision : a researcher conducted an experiment to see if specific eye exercises can improve peripheral vision.nbsp a random

In a weekly coordination meeting several senior : in a weekly coordination meeting several senior investigators from the state crime lab request that ab investigative

Assume youve the functions fx x2 and gx 2x both with : assume youve the functions fx x2 and gx 2x both with domain x ge 0. which function will increase faster on this

Prepare a 700-1050-word paper in which you analyze the : with your instructors approval choose a current federal state or local issue that directly affects public policy

Formulate the corresponding coffee-machine decision problem : meeting rooms on university campuses may or may not contain coffee machines. we would like to ensure that every meeting

Ab investigative services abis has been contacted by a : ab investigative services abis has been contacted by a prominent state law enforcement agency concerning the need to

In your analysis be sure to analyze the impact that cyber : write a 700-1400-word paper in which you research a recent article focusing on cyber-crime. in your analysis be sure to

What are the potential hearings that might be involved in : scenariojesse james a 20-year old was arrested for killing a police officer. as a newly elected prosecutor you are

Be sure to compare and contrast the various international : write a 1050-1400-word paper in which you identify the various major global crimes and criminal issues that have a

User Account

All Pages