Find a graph that has smallest diameter & average shortest path length given an order and a degree.
News
- 2019-11-29: Publicated the presentation slides and the pictures of the Graph Golf Workshop!
- 2019-11-26: The Graph Golf Workshop had been successfully held!
- 2019-11-26: NII News Release for Graph Golf 2019 has published! (Japanese)
- 2019-11-13: Listed the related publications, presentations and softwares.
- 2019-10-21: Announced the award winners and the workshop program!
-
2019-10-16:Some of the graphs are not available for downloads due to a technical issue.2019-10-17: Solved. - 2019-10-15: 54 new solutions! Now we concluded the 2019 competition! Check out the final rankings!
- 2019-10-07: 0 new solution!
- 2019-09-30: 2 new solutions!
- 2019-09-23: 1 new solution!
- 2019-09-16: 4 new solutions!
- 2019-09-09: 0 new solution!
- 2019-09-02: 2 new solutions!
- 2019-08-26: 1 new solution!
- 2019-08-19: 3 new solutions!
- 2019-08-12: 1 new solution!
- 2019-08-05: 3 new solutions!
- 2019-07-29: 66 new solutions!
- 2019-07-29: Tightened the lower bound of diameter and ASPL for grid graphs. Updated the problem page and the rules page accordingly. Re-calculated the gaps using the tigher bound. A program for calculating the tigher bound is provided.
- 2019-07-22: 1245 solutions accepted! Now we enter the open submissions period!
- 2019-05-29: Corrected the definition of ASPL gap in the rules page: "÷ L" was removed.
- 2019-05-13: Started accepting submissions!
- 2019-04-29: Submission will be accepted from May 13.
- 2019-04-26: Announced the 2019 competition!
Archives
Update 2019-11-29
Welcome!
Graph Golf 2019, an online programming competition in the field of graph theory since 2015 seeking for small-diameter graphs, has successfully finished! The top-ranked challengers will be invited and awarded in an international conference held on Nov. 26 in Nagasaki, Japan. You are welcome to attend the conference!
Pickup 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)?
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.
Let me challenge!
The 2019 contest has finished. We are planning the 2020 contest. Stay tuned!
Schedule
- 2019-05-13: Closed submission period starts
- 2019-07-22: Open submission period starts
- 2019-10-14: Submission period ends (deadline 2019-10-14 23:59:59 UTC)
- 2019-10-21: Awards notification
- 2019-11-26 (tentative): Workshop in CANDAR'19