![Mcqmate logo](https://mcqmate.com/images/logos/logo-black.png)
![Mcqmate logo](https://mcqmate.com/images/logos/logo-white.png)
McqMate
Q. |
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? |
A. | Both DHAM3 and SHAM3 are NP-hard |
B. | SHAM3 is NP-hard, but DHAM3 is not |
C. | DHAM3 is NP-hard, but SHAM3 is not |
D. | Neither DHAM3 nor SHAM3 is NP-hard |
Answer» A. Both DHAM3 and SHAM3 are NP-hard |
View all MCQs in
Theory of Computation and Compiler DesignNo comments yet