Close
Register
Close Window

OpenDSA Stand-alone Modules

Chapter 0 modules

Show Source |    | About   «  0.223. Reduction of Independent Set to Vertex Cover   ::   Contents   ::   0.225. Reduction of Hamiltonian Cycle to Traveling Salesman  »

Reduction of 3-SAT to Hamiltonian Cycle

1. 3-SAT to Hamiltonian Cycle

The following slideshow shows that an instance of 3-CNF Satisfiability problem can be reduced to an instance of Hamiltonian Cycle problem in polynomial time.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

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

   «  0.223. Reduction of Independent Set to Vertex Cover   ::   Contents   ::   0.225. Reduction of Hamiltonian Cycle to Traveling Salesman  »

nsf
Close Window