Close
Register
Close Window

Show Source |    | About   «  28.15. Reduction of 3-SAT to Clique   ::   Contents   ::   28.17. Reduction of Independent Set to Vertex Cover  »

28.16. Reduction of Clique to Independent Set

28.16.1. Clique to Independent Set

The following slideshow shows that an instance of Clique problem can be reduced to an instance of Independent Set problem 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.

   «  28.15. Reduction of 3-SAT to Clique   ::   Contents   ::   28.17. Reduction of Independent Set to Vertex Cover  »

nsf
Close Window