Graph Golf

The Order/degree Problem Competition

Find a graph that has smallest diameter & average shortest path length given an order and a degree.

News

Archives

Best solutions

Update 2016-09-26

Show table

Order Degree Diameter ASPL ASPL Gap Improve
36 3 4 3.067 0.312% 12.773% list
64 8 3 1.927 2.860% 13.030% list
96 3 6 4.272 1.723% 13.748% list
256 8 4 2.736 0.674% 5.600% list
300 7 4 3.012 7.096% 5.701% list
384 3 9 6.226 2.644% 6.980% list
512 8 4 3.111 4.876% 5.277% list
1024 3 11 7.679 2.007% 5.159% list
1024 8 5 3.505 0.617% 3.033% list
1024 11 4 3.059 6.538% 4.020% list
1024 32 3 1.998 1.479% 16.597% list
1560 40 3 2.038 3.236% 14.441% list
1800 7 5 4.078 7.259% 2.680% list
3250 57 3 2.070 4.417% 13.800% list
10000 7 7 5.060 5.790% 1.600% list
10000 11 5 4.107 6.259% 1.521% list
10000 20 4 3.376 5.634% 1.515% list
100000 7 8 6.392 2.832% 0.371% list
100000 11 6 5.147 5.810% 0.392% list
100000 20 5 4.133 5.455% 0.610% list

Show complete list

Motivation

Graph design has a rich variety of application fields of computer systems. In particular, it is just meeting a network design of future supercomputers and future high-end datacenters in terms of hop counts, since their networks are topologically modeled as undirected regular graphs. Low latency is preconditioned on small hop counts, but existing network topologies have hop counts much larger than theoretical lower bounds. Therefore, computer network designers desire to find a graph that has a small number of hops between any pair of nodes. How to minimize the diameter and the average shortest path length (ASPL) of a graph given the order (the number of nodes) and the degree (the number of edges at each node)?

Learn more

Competition

Graph Golf is an international competition of the order/degree problem since 2015. It is conducted with the goal of making a catalog of smallest-diameter graphs for every order/degree pair. Anyone in the world can take part in the competition by submitting a graph. Outstanding authors were awarded in CANDAR'16, an international conference held in Higashi-hiroshima, Japan, in November 2016.

Learn more

Let me challenge!

The 2017 competition will open in June 2017. Stay tuned!

Learn more