Graph Golf

The Order/degree Problem Competition

Rules 2015

Update 2015-07-06

The 2015 competition consists of two categories:

Widest improvement award
The widest improvement award goes to the authors who find the largest number of best solutions. The best solution means a graph with the smallest diameter, and with the smallest average shortest path length (ASPL) among those with the same diameter, for each order/degree pair. Formally speaking, we calculate score = 10000k + l, where k is the diameter and l is the ASPL, and pick the graph with the lowest score as the best solution.
Deepest improvement award
The deepest improvement award goes to the authors who achieve the smallest ASPL gap over all the order/degree pairs. The ASPL gap is shown in percentage on the home page and in raw value on the solutions page. The ASPL gap is calculated as gap = (lL) ÷ L, where l is the ASPL of the graph and L is the lower bound of l calculated as in . So far we have gap = 0.0 for some order/degree pairs; thus the Deepest improvement award goes to the authors who achieve the zero ASPL gap.

For the 2015 competition, orders n = [16, 64, 256, 4096, 10000] and degrees d = [3, 4, 16, 23, 60, 64] are featured. Only those graphs with the featured orders and degrees will be considered for the awards.

All the submitted graphs will be publicated on the solutions page and the best solutions will be highlighted on the home page. An author can choose whether to disclose his/her graphs on the solutions page before the submission deadline. After the deadline, all the graph files will be made available for download.