3 ms·
A naive greedy algorithm will eventually find a situation where the two nodes with the highest degrees are already connected. Another place where a simple greed
by dangerlibrary 13y ago
A naive greedy algorithm will eventually find a situation where the two nodes with the highest degrees are already connected. Another place where a simple greedy algorithm falls down is a field of many nodes with the same degree, where the greedy algorithm doesn't give information about which two to connect. I think the problem is a bit deeper than it seems in the first few iterations.
- ajanuary 13y agoYou're correct, I didn't specify it well enough. Pick the node with the highest unassigned degree, connect it to the other unconnected nodes with the highest unassigned degrees (where unassigned degree is the difference between the target degree and the degree of edges we've assigned in previous iterations) I don't fully understand your second point. If there isn't a requirement to create a connected graph it can pick arbitrarily between nodes of equal unassigned degrees. [1] My brain is too tired to come up with a better term than unassigned