Please help with the following ONLY problems 2, 4, and question 5 (if you can estimate time complexity of straightforward algorithm). (will leave a like)
Please help with the following ONLY problems 2, 4, and question 5 (if you can estimate time complexity of straightforward
(will leave a like)
Given a graph G, find the smallest integer k such that the vertex set V of G contains a set A consisting of k elements satisfying the condition: for each edge of G at least one of its ends is in A. The size of the problem is the number n of vertices in G.
1. Suggest a natural greedy algorithm for the problem.
2. Make sure (by estimating the time complexity) that the suggested greedy algorithm is
polynomial (its running time is estimated from above by some power of the size of the problem).
3. Find an instance for which the suggested greedy algorithm gives an erroneous answer.
4. Suggest a (straightforward) algorithm which solves the problem correctly.
5. Estimate the time complexity of the straightforward algorithm.
Greedy algorithm posted below:
Step by step
Solved in 2 steps
