The Order/degree Problem Competition

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

- 2018-12-05: Published the pictures and presentation slides at our workshop in CANDAR '18.
- 2018-11-28: Our workshop in CANDAR '18 finished successfully!
- 2018-11-12: Updated create-random.py to support NetworkX v2.
- 2018-10-22: Announced the award winners and our workshop in CANDAR '18.
- 2018-10-15: 75 new solutions! Submission period ends. Submissions will be reviewed and awarded authors will be notified on Oct 22.
- 2018-10-08: 23 new solutions!
- 2018-10-01: 11 new solutions!
- 2018-09-24: 1 new solution!
- 2018-09-17: 0 new solution
- 2018-09-10: 16 new solutions!
- 2018-09-03: 1 new solution!
- 2018-08-27: 5 new solutions!
- 2018-08-20: 10 new solutions!
- 2018-08-13: 4 new solutions!
- 2018-08-06: 1 new solution!
- 2018-07-30: 13 new solutions!
- 2018-07-25: Fixed a bug. We are sorry for not properly nominating the solutions submitted within the closed submission period.
- 2018-07-23: 75 solutions accepted. Now we enter the open submission period!
- 2018-05-14: Submission period starts!
- 2018-04-26: Announced the 2018 competition!

Update 2018-12-05

Graph Golf 2018 has successfully been completed! Winners presented their techniques in our workshop in CANDAR '18 (slides available).

The next year's competition will start in May 2019. Stay tuned!

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

The 2019 competition will start in May 2019. Stay tuned!

- 2018-05-14: Closed submission period starts
- 2018-07-23: Open submission period starts
- 2018-10-14: Submission period ends (deadline 2018-10-14 23:59:59 UTC)
- 2018-10-22: Awards notification
- 2018-11-27: Workshop in CANDAR'18