Close
Register
Close Window

Show Source |    | About   «  28.18. Reduction of 3-SAT to Hamiltonian Cycle   ::   Contents   ::   28.20. Coping with NP-Complete Problems  »

28.19. Reduction of Hamiltonian Cycle to Traveling Salesman

28.19.1. Hamiltonian Cycle to Traveling Salesman

The following slideshow shows that an instance of Hamiltonian Cycle problem can be reduced to an instance of Traveling Salesman problem in polynomial time.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Traveling Salesman problem.

   «  28.18. Reduction of 3-SAT to Hamiltonian Cycle   ::   Contents   ::   28.20. Coping with NP-Complete Problems  »

Close Window