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

Update 2019-05-13

Welcome!

Graph Golf 2019 features 22 graphs!

Category Order n Degree d Length r Note
General 50 4
General 512 4
General 512 6
General 1024 4
General 1726 30
General 4855 15 Non-regular
General 9344 6
General 65536 6
General 100000 8
General 1000000 16
General 1000000 32
Grid 5x5 4 2
Grid 5x10 4 2
Grid 10x10 4 2
Grid 10x10 6 3
Grid 10x10 8 4
Grid 20x20 4 2
Grid 20x20 6 3
Grid 20x20 8 4
Grid 100x100 4 2
Grid 100x100 6 3
Grid 100x100 8 4

All solutions

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 are awarded in CANDAR'19, an international conference held in Nagasaki, Japan, in November 2019.

Learn more

Let me challenge!

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

Learn more

Schedule