Close
Register
Close Window

Senior Algorithms

Chapter 6 Limits to Computing

Show Source |    | About   «  6.16. Reduction of Independent Set to Vertex Cover   ::   Contents   ::   6.18. Reduction of Clique to Independent Set  »

6.17. Reduction of 3-SAT to Hamiltonian Cycle

6.17.1. 3-SAT to Hamiltonian Cycle

The following slideshow shows that an instance of the 3-CNF Satisfiability (3-SAT) problem can be reduced to an instance of Hamiltonian Cycle in polynomial time. A trivial change in the construction will allow reduction from 3-SAT to the Hamiltonian Path problem.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Hamiltonian Cycle problem.

   «  6.16. Reduction of Independent Set to Vertex Cover   ::   Contents   ::   6.18. Reduction of Clique to Independent Set  »

Close Window