Hamiltonian Path Problem Multiple choice Questions and Answers (MCQs)

DOWNLOAD FREE PDF <<CLICK HERE>>

Hamiltonian Path Problem Multiple choice Questions and Answers (MCQs)

Congratulations - you have completed Hamiltonian Path Problem Multiple choice Questions and Answers (MCQs).

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 6 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Who formulated the first ever algorithm for solving the Hamiltonian path problem?
A
Martello
B
Monte Carlo
C
Leonard
D
Bellman
Question 6 Explanation: 
The first ever problem to solve the Hamiltonian path was the enumerative algorithm formulated by Martello.

Question 7 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
In what time can the Hamiltonian path problem can be solved using dynamic programming?
A
O(N)
B
O(N log N)
C
O(N2)
D
O(N2 2N)
Question 7 Explanation: 
Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N2 2N).

Question 8 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.
A
true
B
false
Question 8 Explanation: 
According to a handshaking lemma, in graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.

Question 9 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
A
Karp
B
Leonard Adleman
C
Andreas Bjorklund
D
Martello
Question 9 Explanation: 
Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of Hamiltonian cycles.

Question 10 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
For a graph of degree three, in what time can a Hamiltonian path be found?
A
O(0.251n)
B
O(0.401n)
C
O(0.167n)
D
O(0.151n)
Question 10 Explanation: 
For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251n).

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 10 questions to complete.

DOWNLOAD FREE PDF <<CLICK HERE>>