3 ms·

A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest de

A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.

PeterSmit 13y ago
Or connect the node with the highest degree with the node with the lowest degree.
- ajanuary 13y ago
  I just tried this and several times the highest degree was already connected with the lowest degree, so I either had to pick another highest degree node (if there was a tie), pick the next highest degree and connect it with the lowest degree, or pick the next lowest degree and connect it with the highest degree. They all seemed to work out okay. I find it interesting that yours appears simpler on the face of it, but has more edge cases. Seems like mine would be simpler if you were actually writing out the steps properly.
- darkmighty 13y ago
  Not only that but also connect the highest with greatest connectivity to the lowest with greatest connectivity to avoid "orphan" nodes.
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 ago
  You'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
gjm11 13y ago
This is in fact the Havel-Hakimi algorithm.

A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.

PeterSmit 13y ago

Or connect the node with the highest degree with the node with the lowest degree.

ajanuary 13y ago
I just tried this and several times the highest degree was already connected with the lowest degree, so I either had to pick another highest degree node (if there was a tie), pick the next highest degree and connect it with the lowest degree, or pick the next lowest degree and connect it with the highest degree. They all seemed to work out okay. I find it interesting that yours appears simpler on the face of it, but has more edge cases. Seems like mine would be simpler if you were actually writing out the steps properly.
darkmighty 13y ago
Not only that but also connect the highest with greatest connectivity to the lowest with greatest connectivity to avoid "orphan" nodes.

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 ago
You'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

gjm11 13y ago

This is in fact the Havel-Hakimi algorithm.