Graph Golf

The Order/degree Problem Competition

Rules 2016

Update 2016-05-25

The 2016 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 = 100000k + 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 largest improvement in ASPL gap over all the order/degree pairs. 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]. The improvement is calculated as (la − lb) ÷ L, where la is the ASPL achieved by the author and lb is the ASPL of the random topology provided as a baseline.

For the 2016 competition, the order/degree pairs (n, d) = (36, 3), (64, 8), (96, 3), (256, 8), (300, 7), (384, 3), (512, 8), (1024, 3), (1024, 8), (1024, 11), (1024, 32), (1560, 40), (1800, 7), (3250, 57), (10000, 7), (10000, 11), (10000, 20), (100000, 7), (100000, 11), (100000, 20) are featured. Only those graphs with the featured orders and degrees will be considered for the awards. However, we also welcome graphs with any order/degree pair.

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

Publication schedule and tie-breaking rule

At the beginning, solutions accepted by 2016-06-26 23:59 UTC are reviewed and publicated on 2016-06-27. Afterwards, solutions accepted within a week are reviewed and publicated every Monday. Note that a week begins at Monday 0:00 UTC and ends at Sunday 23: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 publicated at the earliest time will be nominated for the awards. If there are two or more such graphs publicated at the same time, all of them will be nominated.

Important dates

© 2015-2021 National Institute of Informatics