Register

Data Structures and Algorithms

Chapter 11 Limits to Computing (optional)

Show Source | | About « 11.15. Reduction of 3-SAT to Clique (optional) (WORK IN PROGRESS) :: Contents :: 11.17. Reduction of Independent Set to Vertex Cover (optional) (WORK IN PROGRESS) »

11.16. Reduction of Clique to Independent Set (optional) (WORK IN PROGRESS)¶

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

Proficient

Saving...

Error Saving

Server Error
Resubmit

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

Contact Us || Privacy | | License « 11.15. Reduction of 3-SAT to Clique (optional) (WORK IN PROGRESS) :: Contents :: 11.17. Reduction of Independent Set to Vertex Cover (optional) (WORK IN PROGRESS) »