DOI
https://doi.org/10.25772/XJCB-EQ20
Defense Date
2011
Document Type
Thesis
Degree Name
Master of Science
Department
Mathematical Sciences
First Advisor
Craig Larson
Abstract
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.
Rights
© The Author
Is Part Of
VCU University Archives
Is Part Of
VCU Theses and Dissertations
Date of Submission
September 2011