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.
Paper#72814 | Written in 18-Jul-2015Price : $22