[Solved]: Algorithm to extract the subgraph of all nodes with degree at least four

Problem Detail: 

I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which have degree of at least 4. I think I've developed an algorithm. It uses an object called Node, which can store an integer for the degree of the node and a list of that node's neighboring nodes.

1. For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
2. Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
3. Search the list in $O(|V|)$ time and find the node with smallest degree. If >4, return. If <4, visit the node's neighbors, reduce their degrees by one, and remove this node from their list of neighbors. Then remove this node from the graph, in worst case $O(|V|)$ time.
4. Repeat step 3. At worst $O(|V|)$ times.

If anyone is wondering, I'm doing this for a Civilization-esque game I'm making. I want to be able to separate cities that are part of major trade routes from minor ones.

Now, I think this algorithm is correct, but I'm not happy with its running time. If I'm not mistaken, it's $O(|V|^2)$, correct? Is there a way to make this more efficient?

Asked By : user30206

Answered By : Yuval Filmus

The object you are trying to find is known in graph theory as the 4-core. Batagelj and Zaveršnik give a simple linear time algorithm for finding the $k$-core for any given $k$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40919

 Ask a Question

 Download Related Notes/Documents