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

Your account

login

Search

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

Description

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

graphs.zip
2.2 MB, S3 ETag 78fc5c06d68274c2717b045454a18d43-1, downloads: 62
The file hash is calculated from the formula
hexmd5(md5(part1)+md5(part2)+...)-{parts_count} where a single part of the file is 512 MB in size.

Example script for calculation:
https://github.com/antespi/s3md5
download file graphs.zip

File details

License:
Creative Commons: by 4.0 open in new tab
CC BY
Attribution

Details

Year of publication:
2020
Verification date:
2020-12-17
Creation date:
2020
Dataset language:
English
Fields of science:
  • mathematics (Natural sciences)
DOI:
DOI ID 10.34808/55ns-an76 open in new tab
Verified by:
Gdańsk University of Technology

Keywords

References

Cite as

Authors

seen 338 times