Implement VERTEX COVER; that is, given graph (mathbf{G}) and integer (k), answer the question of whether or
Question:
Implement VERTEX COVER; that is, given graph \(\mathbf{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 that checks 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 through the use of 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.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Question Posted: