Page 1 of 1
= Q7. Let G = (V, E) be an undirected graph, where V is the set of vertices and E is the set of edges of G, respectively
Posted: Fri Apr 29, 2022 6:56 am
by answerhappygod
- Q7 Let G V E Be An Undirected Graph Where V Is The Set Of Vertices And E Is The Set Of Edges Of G Respectively 1 (333.66 KiB) Viewed 26 times
= Q7. Let G = (V, E) be an undirected graph, where V is the set of vertices and E is the set of edges of G, respectively. Let n = \N and m = \E]. Given a subset S of V, the subgraph induced in G by S is defined by G[S] = (S, Es), where Es consists of all the edges in E that have both endpoints in S, i.e., for any edge (u, v) in E, if u and v are both in S, then (u, v) is also in Es. The k-core of G is the largest subgraph H= (VH, Eh) of G induced by the vertex set VH such that a vertex v in VH has at least k adjacent vertices in H. Design an algorithm to compute the k-core of G with a given k. The time complexity of your algorithm should not be higher than O((m + n) log n). (20 marks) - +