A collection of directed graphs for the minimum cycle mean weight computation - Open Research Data - MOST Wiedzy


A collection of directed graphs for the minimum cycle mean weight computation


This dataset contains definitions of the 16 directed graphs with weighted edges that were described in the following paper: Paweł Pilarczyk, A space-efficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349--355, DOI: 10.22436/jmcs.020.04.08, URL: http://dx.doi.org/10.22436/jmcs.020.04.08
These are sparse graphs that contain different numbers of vertices, varying from 1,000 to 16,000, and an average of 3 edges per vertex. The minimum mean weight of cycles in each of the graphs is positive, and varies between 0.427 and 0.646. These graphs were obtained as a rigorous numerical representation of a quadratic map with bounds on its derivative, as mentioned in the above-mentioned paper.
The graphs are encoded using text format. Each line that begins whith the semicolon is a comment. The graph is encoded by means of a list of edges. Vertices are identified by integer numbers. Weighted edges are defined in the format "N -> M [w]", where N is the beginning vertex and M is the ending vertex of the edge, and w is the weight written in the format of a floating-point number. At the beginning of the file, the first comment indicates the number of vertices in the graph, although this might be inferred from the numbers of vertices that appear in the edges. At the end of the file, there is a comment indicating the end of the definition of the graph.

Dataset file

2.2MB, MD5 78fc5c06d68274c2717b045454a18d43-1, downloads: 2


Year of publication:
Creation date:
Dataset language:
Fields of science:
  • Mathematics (Natural sciences)
10.34808/55ns-an76 open in new tab
Verified by:
Gdańsk University of Technology



seen 61 times