Close
Register
Close Window

Senior Algorithms

Chapter 6 Limits to Computing

Show Source |    | About   «  6.17. Reduction of 3-SAT to Hamiltonian Cycle   ::   Contents   ::   6.19. Reduction of Hamiltonian Cycle to Traveling Salesman  »

6.18. Reduction of Clique to Independent Set

6.18.1. Clique to Independent Set

The following slideshow shows that an instance of CLIQUE can be reduced to an equivalent instance of INDEPENDENT SET in polynomial time.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Independent Set problem.

   «  6.17. Reduction of 3-SAT to Hamiltonian Cycle   ::   Contents   ::   6.19. Reduction of Hamiltonian Cycle to Traveling Salesman  »

© Copyright 2011-2023 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Nov 18, 2024. Created using Sphinx 5.2.1.
Close Window