The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as possible.My question is that I want to find the time complexity of the following algorithm (when applied on $N \times N$ grid graphs):
Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm
graphs;graph theory;greedy algorithms
Let's analyze the runtime. In each iteration of the loop we look for the maximum weight node. If you do this naively, you look at all nodes. By using a clever data structure you could speed this up. Adding the node to S takes constant time for all reasonable set data structures. Now we remove $v_i$ and its neighbors. This can be done in time proportional to the number of incident edges at $v_i$ and at its neighbors, for reasonable graph representations, e.g. an adjacency list.In your comment you stated that you had problems analyzing the algorithm because you didn't know the number of iterations of the loop. You could conservatively assume that you remove only $v_i$ itself to get a runtime of $O(|V| \times $finding the max$)$, so $O(|V|^2)$. Since $G$ is a grid graph, each node has degree at most four. So even if you assume optimistically that you remove five nodes in each iteration you get the same asymptotic runtime.