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

Best solutions

Update 2017-03-06

Will be announced after 2017-06-26. Show baseline

Order Degree Length Diameter ASPL ASPL Gap
32 5 4 2.280 12.202% list
256 18 3 2.188 13.407% list
576 30 3 2.141 9.920% list
1344 30 3 2.483 7.586% list
4896 24 4 2.949 2.486% list
9344 10 6 4.311 7.422% list
88128 12 7 4.911 2.724% list
98304 10 7 5.383 4.410% list
100000 32 5 3.717 1.240% list
100000 64 4 3.035 2.580% list
16 3 2 9 3.792 72.348% list
256 3 3 22 8.583 53.596% list
256 3 4 18 7.890 41.194% list
256 3 15 13 6.274 12.275% list
256 6 3 13 5.319 71.254% list
256 6 4 10 4.550 46.480% list
256 6 15 5 3.396 9.356% list
256 15 3 10 4.199 103.938% list
256 15 4 8 3.465 68.298% list
256 15 15 4 2.374 15.290% list
10000 3 6 59 23.753 120.449% list
10000 3 18 26 13.147 22.017% list
10000 3 33 19 11.677 8.367% list
10000 9 6 36 13.570 208.503% list
10000 9 18 14 6.175 40.384% list
10000 9 33 9 4.924 11.937% list
10000 28 6 34 11.826 305.154% list
10000 28 18 12 4.821 65.188% list
10000 28 33 7 3.534 21.067% list

Show ranking

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'17, an international conference held in Aomori, Japan, in November 2017.

Learn more

Let me challenge!

You're welcome! Go to the submission page and follow the instructions.

Learn more