Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Entire DC Network
A Horizontal Edges Bound For The Independence Number Of A Graph, Michelle Grigsby
A Horizontal Edges Bound For The Independence Number Of A Graph, Michelle Grigsby
Theses and Dissertations
The independence number alpha of a graph is the size of a maximum independent set of vertices. An independent set is a set of vertices where every pair of vertices in non-adjacent. This number is known to be hard to compute. The bound we worked with is defined as epsilon = max[e(v)-eh(v)] over all the vertices in the vertex set, V(G). e(v) is the number of vertices at even distance from v. eh(v) is the number of edges both of whose endpoints are at even distance from v. Epsilon can be calculated in polynomial time. Siemion Fajtlowicz proved that alpha …
The Independent Set Decision Problem Is Np-Complete, Andrew Bristow Iv
The Independent Set Decision Problem Is Np-Complete, Andrew Bristow Iv
Theses and Dissertations
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 …