UTpaper

Free mock tests & test series

Question 48Asked in UGC NET Computer Science, June 2015 (Paper II & III, Selected Questions)

The travelling salesman problem can be solved in :

  1. APolynomial time using dynamic programming algorithm
  2. BPolynomial time using branch-and-bound algorithm
  3. CExponential time using dynamic programming algorithm or branch-and-bound algorithm
  4. DPolynomial time using backtracking algorithm
Show answerHide answer

Correct answer: (C) Exponential time using dynamic programming algorithm or branch-and-bound algorithm

Explanation

It will be solved by using branch and bound technique. The travelling salesman problem is NP- complete problem. It can also be solved by- one of the earliest application of dynamic programming is the Held-Karp algorithm to solve TSP in time O(n².2ⁿ).

From UGC NET Computer Science PYQ, June 2015 (Paper II & III, Selected Questions)

This is question 48 of UGC NET Computer Science PYQ, June 2015 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.