The Order/degree Problem Competition

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

- 2016-11-28: Reported the workshop in CANDAR'16
- 2016-09-26: Announced the final ranking with 11 new solutions!
- 2016-09-25: Submission closed
- 2016-09-20: Reported the event in FIT 2016 (in Japanese)
- 2016-09-20: Reported the special session in NOCS 2016
- 2016-09-19: 15 new solutions!
- 2016-09-12: 0 new solution
- 2016-09-05: 0 new solution
- 2016-08-29: 6 new solutions!
- 2016-08-22: 0 new solution
- 2016-08-15: 0 new solution
- 2016-08-08: 0 new solution
- 2016-08-02: 0 new solution
- 2016-07-25: Fixed incorrect week numbers in the ranking
- 2016-07-25: 1 new solution!
- 2016-07-18: 3 new solutions!
- 2016-07-11: 2 new solutions!
- 2016-07-04: 13 new solutions!
- 2016-06-27: 80 new solutions!
- 2016-06-15: An article in the Nikkan Kogyo Shimbun (in Japanese)
- 2016-06-13: NOCS 2016 special session "Small-Diameter Graphs for Low-Latency NoCs" is announced
- 2016-06-09: NII news release for the 2016 competition (in Japanese) [PDF]
- 2016-05-27: The 2016 competition opens! The early-bird period ends on 2016-06-26. Check out the rules
- 2016-05-24: FIT 2016 event "Pursuit of Small-diameter Graphs" is announced (in Japanese).
- 2016-01-07: Reported the 2015 Graph Golf Workshop

Update 2016-09-26

Order | Degree | Diameter | ASPL | ASPL Gap | Improve | |
---|---|---|---|---|---|---|

36 | 3 | 4 | 3.067 | 0.312% | 12.773% | list |

64 | 8 | 3 | 1.927 | 2.860% | 13.030% | list |

96 | 3 | 6 | 4.272 | 1.723% | 13.748% | list |

256 | 8 | 4 | 2.736 | 0.674% | 5.600% | list |

300 | 7 | 4 | 3.012 | 7.096% | 5.701% | list |

384 | 3 | 9 | 6.226 | 2.644% | 6.980% | list |

512 | 8 | 4 | 3.111 | 4.876% | 5.277% | list |

1024 | 3 | 11 | 7.679 | 2.007% | 5.159% | list |

1024 | 8 | 5 | 3.505 | 0.617% | 3.033% | list |

1024 | 11 | 4 | 3.059 | 6.538% | 4.020% | list |

1024 | 32 | 3 | 1.998 | 1.479% | 16.597% | list |

1560 | 40 | 3 | 2.038 | 3.236% | 14.441% | list |

1800 | 7 | 5 | 4.078 | 7.259% | 2.680% | list |

3250 | 57 | 3 | 2.070 | 4.417% | 13.800% | list |

10000 | 7 | 7 | 5.060 | 5.790% | 1.600% | list |

10000 | 11 | 5 | 4.107 | 6.259% | 1.521% | list |

10000 | 20 | 4 | 3.376 | 5.634% | 1.515% | list |

100000 | 7 | 8 | 6.392 | 2.832% | 0.371% | list |

100000 | 11 | 6 | 5.147 | 5.810% | 0.392% | list |

100000 | 20 | 5 | 4.133 | 5.455% | 0.610% | list |

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 were awarded in CANDAR'16, an international conference held in Higashi-hiroshima, Japan, in November 2016.

The 2017 competition will open in June 2017. Stay tuned!