I have an undirected graph represented by a list of nodes and a list of edges. W

Question

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?

Explanation / Answer

The object you are trying to find is known in graph theory as the 4-core. Batagelj and Zaver

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.