Edit Question - KnowledgeHub

Title Body

Here is an excise for graph. Given an undirected graph G with n vertices and m edges, and an integer k, give an O(m + n) algorithm that finds the maximum induced subgraph H of G such that each vertex in H has degree ≥ k, or prove that no such graph exists. An induced subgraph F = (U, R) of a graph G = (V, E) is a subset of U of the vertices V of G, and all edges R of G such that both vertices of each edge are in U. My initial idea is like this: First, this excise actually asks that we have all vertices S whose degrees are bigger than or equal to k, then we remove vertices in S who don't have any edge connected to others. Then the refined S is H, in which all vertices have degree >= k and the edges between them is R. In addition, it asks O(m+n), so I think I need to a BFS or DFS. Then I get stuck. In BFS, I can know the degree of a vertex. But once I get the degree of v (a vertex), I don't know other connected vertices except for its parent. But if the parent doesn't have degree >= k, I can't eliminate v as it may still be connected with others. Any hints? Edit: According to the answer of @Michael J. Barber, I implemented it and update the code here: Can anyone have a look at the key method of the codes public Graph kCore(Graph g, int k) ? Do I do it right? Is it O(m+n)? class EdgeNode { EdgeNode next; int y; } public class Graph { public EdgeNode[] edges; public int numVertices; public boolean directed; public Graph(int _numVertices, boolean _directed) { numVertices = _numVertices; directed = _directed; edges = new EdgeNode[numVertices]; } public void insertEdge(int x, int y) { insertEdge(x, y, directed); } public void insertEdge(int x, int y, boolean _directed) { EdgeNode edge = new EdgeNode(); edge.y = y; edge.next = edges[x];

Tags (comma-separated) Cancel