(Submitted towards the completion of CS 3013: Artificial Intelligence, in collaboration with Chaitanya Bhojwani and Prerna Jotwani)
In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. Finding a minimum vertex cover is a classic optimization problem in computer science and is a typical example of an NP-hard optimization problem.
The vertex cover V' of an undirected graph G=(V,E) is a subset of V such that uv in E -> u in V' v v in V'
The mimimum vertex cover is the smallest vertex cover possible.
In Dahiya et al. (ICMIRA 2013) an algorithm is proposed and tested on example cases. We have modified this algorithm and improved the results for two example cases.
Refer to report.pdf for more details.