Close
Register
Close Window

F17 OpenDSA entire modules

Chapter 34 Limits to Computing

Show Source |    | About   «  34.16. Reduction of Clique to Independent Set   ::   Contents   ::   34.18. Reduction of 3-SAT to Hamiltonian Cycle  »

34.17. Reduction of Independent Set to Vertex Cover

34.17.1. Independent Set to Vertex Cover

The following slideshow shows that an instance of Independent Set problem can be reduced to an instance of Vertex Cover problem in polynomial time.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Vertex Cover problem.

   «  34.16. Reduction of Clique to Independent Set   ::   Contents   ::   34.18. Reduction of 3-SAT to Hamiltonian Cycle  »

nsf

© Copyright 2016 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Sep 26, 2017. Created using Sphinx 1.2.
Close Window