The Order/degree Problem Competition

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

- 2017-11-27: Reported the Graph Golf Workshop held in conjunction with CANDAR17
- 2017-11-22: NII news release for the 2017 competition (in Japanese) [PDF]
- 2017-11-16: Announced the program of the Graph Golf Workshop on November 22.
- 2017-09-26: The website experienced a technical trouble. We apologize for the inconvenience.
- 2017-09-25: Announced the Graph Golf Workshop held in conjunction with CANDAR17 in November 19-22 in Aomori, Japan. We are preparing a cute souvenir!
- 2017-09-25: 39 new solutions conclude the 2017 competition! Final rankings are announced in the ranking page!
- 2017-09-18: 43 new solutions!
- 2017-09-11: 23 new solutions!
- 2017-09-04: 2 new solutions!
- 2017-08-28: 12 new solutions!
- 2017-08-25: Fixed some small errors in calculating ASPL for those graphs with loop/multi-edges. The ranking is not affected. We thank Ibuki Kawamata for pointing out the issue.
- 2017-08-21: 7 new solutions!
- 2017-08-14: Fixed a bug in the Deepest Improvement rankings table. We are sorry for displaying incorrect rankings until 2017-08-13.
- 2017-08-14: 17 new solutions!
- 2017-08-07: 37 new solutions!
- 2017-07-31: 25 new solutions!
- 2017-07-24: 7 new solutions!
- 2017-07-18: Fixed the submission form. Now authors can choose to disclose their graph files.
- 2017-07-17: 21 new solutions!
- 2017-07-10: 1 new solution!
- 2017-07-03: 28 new solutions!
- 2017-06-29: Open submission period starts! 6 new solutions are now publicated.
- 2017-03-06: The 2017 competition opens!

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)?

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

The 2018 competition will start in April 2018. Stay tuned!