Given an undirected graph G = (V, E).

Given an undirected graph G = (V,E). A set S subset equal V is a dominating set if every vertex v isinv V 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 algoritlm that attempts to compute a dominating set. Input G = (V,E). Set D = emptyset While V is not empty do let v isinv V be a vertex with largest degree. Add v to D. Remove v and all vertices incident on v from V (and thus from G). Output D. Let m denote number of edges and n denote number of vertices of a graph. Show that above algorithm can be implemented in theta(n^2) time. Improve your implementation (using appropriate data structures) so that it runs in time O((m + n) logn). Above algorithm does not always return a smallest dominating set. However, tills algorithm is a good heuristic that works decently in practice. Give a graph on which above algorithm does not output smallest dominating set