# 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

• 2016-01-07: Reported the 2015 Graph Golf Workshop in the event page
• 2015-12-10: Announced the final rankings for the 2015 competition!
• 2015-10-16: Submission closed! Finalists will be notified by 2015-10-20
• 2015-10-06: Added 2 new solutions! This is the final update before the deadline
• 2015-09-28: Added 3 new solutions!
• 2015-09-21: Added 5 new solutions!
• 2015-09-14: Added 4 new solutions!
• 2015-09-07: Added 6 new solutions!
• 2015-08-31: Added 8 new solutions!
• 2015-08-24: Added 7 new solutions!
• 2015-08-17: Added 17 new solutions!
• 2015-08-10: Added 12 new solutions!
• 2015-08-03: Added 10 new solutions!
• 2015-07-28: Added 5 new solutions! (update delayed due to a maintenance)
• 2015-07-20: Current ranking is now being announced!
• 2015-07-20: Added 2 new solutions!
• 2015-07-13: Added 9 new solutions!
• 2015-07-06: Added 15 new solutions!
• 2015-06-30: Added 11 new solutions! (update delayed due to a network issue)
• 2015-06-23: create-random.py now reports infinity for disconnected graphs
• 2015-06-22: Added 18 new solutions!
• 2015-06-15: Added 22 new solutions!
• 2015-06-11: Publication schedule and tie-breaking rule are defined
• 2015-06-09: Newspaper report (in Japanese)
• 2015-06-08: Added 72 new solutions!
• 2015-06-01: Submission period started
• 2015-05-29: News release (in Japanese) [PDF]
• 2015-04-23: Preliminary release

## Best solutions

Update 2015-12-10

Degree
d
Order n
16 64 256 4096 10000
3
0.000%

0.211%

0.861%

2.928%

3.122%
4
0.962%

0.417%

1.065%

4.373%

3.480%
16 N/A
0.000%

8.020%

8.716%

1.060%
23 N/A
0.000%

0.000%

0.731%

8.675%
60 N/A
0.000%

0.000%

8.975%

0.615%
64 N/A N/A
0.000%

12.994%

1.005%
Legend: Diameter / Average shortest path length (ASPL)
Gap from the lower bound of ASPL (%)
Notes: 1. A random graph is optimal. Submissions with this size will not be awarded.
2. There are no graphs with this size that satisfy the lower bound of diameter and ASPL .

## 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 were awarded in CANDAR'15, an international conference held in Sapporo, Japan, in December 2015.

## Let me challenge!

Please be looking forward to an announcement of the 2016 competition!