Close
Register
Close Window

Data Structures and Algorithms

Chapter 11 Limits to Computing (optional)

Show Source |    | About   «  11.18. Reduction of 3-SAT to Hamiltonian Cycle (optional) (WORK IN PROGRESS)   ::   Contents   ::   11.20. Coping with NP-Complete Problems (optional) (WORK IN PROGRESS)  »

11.19. Reduction of Hamiltonian Cycle to Traveling Salesman (optional) (WORK IN PROGRESS)

11.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.

   «  11.18. Reduction of 3-SAT to Hamiltonian Cycle (optional) (WORK IN PROGRESS)   ::   Contents   ::   11.20. Coping with NP-Complete Problems (optional) (WORK IN PROGRESS)  »

nsf

© Copyright 2016 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Nov 16, 2022. Created using Sphinx 2.4.4.
Close Window