Reference no: EM132115951

Question

Implement the Vertex Cover problem; that is, given graph G and integer k, answer the question of whether or not there is a vertex cover of size k or less.

Begin by using a brute-force algorithm to check all possible sets of vertices of size k to find an acceptable vertex cover, and measure the running time on a number of input graphs.

Then try to reduce the running time using any heuristics you can think of. Next, try to find approximate solutions to the problem in the sense of finding the smallest set of vertices that forms a vertex cover and analysing its running time.

What needs to be handed in

1. A report including

a. A description of your software and hardware environment for developing the project.

b. The design of the algorithm.

c. Testing input data and the results and complexity analysis. You should include some screen shots showing the running scenarios and the running results.

d. A user manual explaining how to run your project.

e. Discussions and reflection on knowledge gained.

f. References.

2. The commented source code and the executable file.