Description
This dataset contains definitions of the 16 directed graphs with weighted edges that were described in the following paper: Paweł Pilarczyk, A spaceefficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349355, 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 abovementioned 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 floatingpoint 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.
Authors
Dataset file
graphs.zip
2.2MB,
MD5 78fc5c06d68274c2717b045454a18d431,
downloads: 2
Details
 Year of publication:
 2020
 Creation date:
 2020
 Dataset language:
 English
 Fields of science:

 Mathematics (Natural sciences)
 License:

CC BYAttribution
 DOI:
 10.34808/55nsan76 open in new tab
 Verified by:
 Gdańsk University of Technology
Keywords
References
seen 61 times