In the 1970's computer scientists developed the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was the first problem to be proved NP-complete in 1971. Since then numerous other hard-to-solve problems have been proved to be in NP-complete. In this paper we will examine the problem of how to find a maximum independent set of vertices for a graph. This problem is known as Maximum Independent Set (MIS) for a graph. The corresponding decision problem for MIS is the question, given an integer K, is there a independent set with at least K vertices? This decision problem is INDEPENDENT SET (IS). The intention of this paper is to show through polynomial transformation that IS is in the set of NP-complete Problems. We intend to show that 3SAT is NP-complete and then using this fact, that IS is NP-complete.
| Identifer | oai:union.ndltd.org:vcu.edu/oai:scholarscompass.vcu.edu:etd-3572 |
| Date | 18 August 2011 |
| Creators | Bristow, Andrew, IV |
| Publisher | VCU Scholars Compass |
| Source Sets | Virginia Commonwealth University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations |
| Rights | © The Author |
Page generated in 0.0021 seconds