Question

For a graph of degree three, in what time can a Hamiltonian path be found?

(a) O(0.251^n)

(b) O(0.401^n)

(c) O(0.167^n)

(d) O(0.151^n)

This question was posed to me in quiz.

This interesting question is from Checksum, Complexity Classes & NP Complete Problems in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

The correct answer is (a) O(0.251^n)

Easy explanation - For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251^n).