Register

UGC NET CSE | Junet 2015 | Part 3 | Question: 32

5,700 views
0 votes
0 votes

The travelling salesman problem can be solved in

  1. Polynomial time using dynamic programming algorithm
  2. Polynomial time using branch-and-bound algorithm
  3. Exponential time using dynamic programming algorithm or branch-and-bound algorithm
  4. Polynomial time using back tracking algorithm
User Avatar

1 Answer

4 votes
4 votes
As per i know travelling salesman problem is a Np hard not p . if the traveling salesman problem can be solved in polynomial time using backtracking then it will become a P . So its false , it cant be solved in polynomial time by deterministic way .
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
1 answer
3
go_editor asked Jul 31, 2016
3,309 views
UGC NET CSE | Junet 2015 | Part 3 | Question: 31
An all-pairs shortest-paths problem is efficiently solved using: Dijkstra's algorithm Bellman-Ford algorithm Kruskal algorithm Floyd-Warshall algorithm
An all-pairs shortest-paths problem is efficiently solved using:Dijkstra's algorithmBellman-Ford algorithmKruskal algorithmFloyd-Warshall algorithm
User Avatar
4 votes
4 votes
3 answers
4
Shubham Sahu asked Jul 12, 2015
3,886 views
UGC NET CSE | Junet 2015 | Part 3 | Question: 35
Let $f(n)$ and $g(n)$ be asymptotically non-negative functions. Which of the following is correct? $\theta (f(n)^*g(n))=min (f(n),g(n))$ $\theta (f(n)^*g(n))=max(f(n),g(n))$ $\theta (f(n)+g(n))=min(f(n),g(n))$ $\theta (f(n)+g(n))=max(f(n),g(n))$
Let $f(n)$ and $g(n)$ be asymptotically non-negative functions. Which of the following is correct?$\theta (f(n)^*g(n))=min (f(n),g(n))$$\theta (f(n)^*g(n))=max(f(n),g(n))...
User Avatar
Link Copied!