Given an undirected graph G = (V. E), with V = {1, 2, . . . ,n). A set S-V is a dominating set if every vertex v EV either belongs to S or is adjacent to a vertex in S. Given a graph, we would like to compute a dominating set of smallest size. Consider the following natural greedy algorithm that attempts to compute a dominating set. Given vE V, let (a) Input G-(V, E) (b) Set D-0 (c) While V is not empty do let vE V be a vertex with largest degree . Add v to D . Remove v and all vertices in N (v) from G (and thus from V) (d) Output D Note: When we remove a vertex r from G, we remove r from V, and all edges that are incident on r from E Using appropriate data structures, design an efficient implementation of the above algorithm and analyze/derive the runtime of your implementation. Express the run-time as a function of number of edges (m) and number of vertices (n). Your grade partly depends on efficiency Remark. The above algorithm is a heuristic. It will not always produce a smallest dom- inating set. Think about graphs on which the above algorithm fails to produce a smallest dominating set Given an undirected graph G = (V. E), with V = {1, 2, . . . ,n). A set S-V is a dominating set if every vertex v EV either belongs to S or is adjacent to a vertex in S. Given a graph, we would like to compute a dominating set of smallest size. Consider the following natural greedy algorithm that attempts to compute a dominating set. Given vE V, let (a) Input G-(V, E) (b) Set D-0 (c) While V is not empty do let vE V be a vertex with largest degree . Add v to D . Remove v and all vertices in N (v) from G (and thus from V) (d) Output D Note: When we remove a vertex r from G, we remove r from V, and all edges that are incident on r from E Using appropriate data structures, design an efficient implementation of the above algorithm and analyze/derive the runtime of your implementation. Express the run-time as a function of number of edges (m) and number of vertices (n). Your grade partly depends on efficiency Remark. The above algorithm is a heuristic. It will not always produce a smallest dom- inating set. Think about graphs on which the above algorithm fails to produce a smallest dominating set