Worst Case running time of the Minimum Vertex Cover Approximation algorithm
-
06-11-2019 - |
题
Considering this factor $2$ minimum vertex cover approximation algorithm :
Repeat while there is an edge:
Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. Delete $u$ and $v$ from the graph. Finally output the candidate cover.
I want to find the worst case running time of this algorithm. Since in a fully connected graph we have $O(n^2)$ edges, then the loop will run at most $O(n^2)$ times.
Here I am not sure what the maximal number of delete operations could be or perhaps for less than $O(n^2)$ edges being processed in the loop there would be some scenario with a large number of delete operations would contribute to the overall complexity.
I want to say naively that in the worst case you simply multiply the max number of edges possible with the max number of delete operations possible (both $O(n^2))$ giving $O(n^4)$, but this seems wrong.
Any insights appreciated.
没有正确的解决方案