**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?**

Martello | |

Monte Carlo | |

Leonard | |

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?**

O(N) | |

O(N log N) | |

O(N^{2}) | |

O(N^{2} 2^{N}) |

Question 7 Explanation:

Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N

^{2}2^{N}).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.**

true | |

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?**

Karp | |

Leonard Adleman | |

Andreas Bjorklund | |

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?**

O(0.251^{n}) | |

O(0.401^{n}) | |

O(0.167^{n}) | |

O(0.151^{n}) |

Question 10 Explanation:

For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251

^{n}). Once you are finished, click the button below. Any items you have not completed will be marked incorrect.

There are 10 questions to complete.