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.
- For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
- Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
- 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.
- 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?