McqMate

Q. |
## 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) |

Answer» A. o(0.251n) | |

Explanation: for a graph of maximum degree three, a hamiltonian path can be found in time o(0.251n). |

678

0

Do you find this helpful?

7

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
- What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
- A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
- In what time can the Hamiltonian path problem can be solved using dynamic programming?
- Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
- A graph is found to be 2 colorable. What can be said about that graph?
- How many Hamiltonian paths does the following graph have?
- How many Hamiltonian paths does the following graph have?
- Hamiltonian path problem is
- Which of the following problems is similar to that of a Hamiltonian path problem?