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 = (l − L) ÷ L, where l is the ASPL of the graph and L is the lower bound of l calculated as in [Cerf 1974]. 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.

Publication schedule and tie-breaking rule

Added 2015-06-11

Solutions are publicated weekly. A week begins at Monday 0:00 UTC and ends at Sunday 23:59 UTC (except for 2015-05-31, which is treated as the same week as 2015-06-01). Solutions accepted within a week are reviewed and publicated every Monday in Japan (by Monday 14:59 UTC).

The first-to-file rule applies to graphs with the same diameter and ASPL. For each order/degree pair, if two or more graphs have the same diameter and the same ASPL, only those submitted in the earliest week will be nominated for the awards. If there are two or more such graphs submitted within the same week, all of them will be nominated.

Important dates

© 2015-2021 National Institute of Informatics