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

Opis

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.

Plik z danymi badawczymi

graphs.zip

2.2 MB, S3 ETag 78fc5c06d68274c2717b045454a18d43-1, pobrań: 61

Hash pliku liczony jest ze wzoru
hexmd5(md5(part1)+md5(part2)+...)-{parts_count} gdzie pojedyncza część pliku jest wielkości 512 MB

Przykładowy skrypt do wyliczenia:
https://github.com/antespi/s3md5

pobierz

Informacje szczegółowe o pliku

Licencja:: otwiera się w nowej karcie

CC BY

Uznanie autorstwa

Informacje szczegółowe

Rok publikacji:

2020

Data zatwierdzenia:

2020-12-17

Data wytworzenia:

2020

Język danych badawczych:

angielski

Dyscypliny:

matematyka (Dziedzina nauk ścisłych i przyrodniczych)

DOI:

10.34808/55ns-an76

Weryfikacja:

Politechnika Gdańska

Słowa kluczowe

Powiązane zasoby

publikacja A space-efficient algorithm for computing the minimum cycle mean in a directed graph

Cytuj jako

Autorzy

wyświetlono 333 razy

Wyszukiwarka