A row generation algorithm for finding optimal burning sequences of large graphs - complementary data

Pereira, Felipe de Carvalho; Rezende, Pedro Jussieu de; Yunes, Tallys Hoover; Morato, Luiz Fernando Batista

Please use this identifier to cite or link to this item: https://doi.org/10.25824/redu/ZGX0H7

DOI:	https://doi.org/10.25824/redu/ZGX0H7
Title:	A row generation algorithm for finding optimal burning sequences of large graphs - complementary data
Subject:	Computer and Information Science
Description:	This dataset contains complementary data to the paper "A Row Generation Algorithm for Finding Optimal Burning Sequences of Large Graphs" [1], which proposes an exact algorithm for the Graph Burning Problem, an NP-hard optimization problem that models a form of contagion diffusion on social networks. Concerning the computational experiments discussed in that paper, we make available: - Four sets of instances; - The optimal (or best known) solutions obtained; - The source code; - An Appendix with additional details about the results. The "delta" input sets include graphs that are real-world networks [1,2], while the "grid" input set contains graphs that are square grids. The directories "delta_10K_instances", "delta_100K_instances", "delta_4M_instances" and "grid_instances" contain files that describe the sets of instances. The first two lines of each file contain: {n} {m} where {n} and {m} are the number of vertices and edges in the graph. Each of the next {m} lines contains: {u} {v} where {u} and {v} identify a pair of vertices that determines an undirected edge. The directories "delta_10K_solutions", "delta_100K_solutions", "delta_4M_solutions" and "grid_solutions" contain files that describe the optimal (or best known) solutions for the corresponding sets of instances. The first line of each file contains: {s} where {s} is the number of vertices in the burning sequence. Each of the next {s} lines contains: {v} where {v} identifies a fire source. The fire sources are listed in the same order that they appear in a burning sequence of length {s}. The directory "source_code" contains the implementations of the exact algorithm proposed in the paper [1], namely, PRYM. Lastly, the file "appendix.pdf" presents additional details on the results reported in the paper. This work was supported by grants from Santander Bank, Brazil, Brazilian National Council for Scientific and Technological Development (CNPq), Brazil, São Paulo Research Foundation (FAPESP), Brazil and Fund for Support to Teaching, Research and Outreach Activities (FAEPEX). Caveat: the opinions, hypotheses and conclusions or recommendations expressed in this material are the sole responsibility of the authors and do not necessarily reflect the views of Santander, CNPq, FAPESP or FAEPEX. References [1] F. C. Pereira, P. J. de Rezende, T. Yunes and L. F. B. Morato. A Row Generation Algorithm for Finding Optimal Burning Sequences of Large Graphs. Submitted. 2024. [2] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. 2024. https://snap.stanford.edu/data [3] Ryan A. Rossi and Nesreen K. Ahmed. The Network Data Repository with Interactive Graph Analytics and Visualization. In: AAAI, 2022. https://networkrepository.com
Authors:	Pereira, Felipe de Carvalho Rezende, Pedro Jussieu de Yunes, Tallys Hoover Morato, Luiz Fernando Batista
URI:	https://doi.org/10.25824/redu/ZGX0H7 https://redu.unicamp.br/dataset.xhtml?persistentId=doi:10.25824/redu/ZGX0H7
Other Identifiers:
Sponsorship:	Conselho Nacional de Desenvolvimento Científico e Tecnológico Conselho Nacional de Desenvolvimento Científico e Tecnológico Fundação de Amparo à Pesquisa do Estado de São Paulo Fundação de Amparo à Pesquisa do Estado de São Paulo
Sponsor ID:	CNPQ: 314293/2023-0 CNPQ: 313329/2020-6 FAPESP: 2023/04318-7 2023/14427-8
Rights:
Date:	11-Nov-2024
Available Data:	13-Nov-2024
Format:
Type:
Publisher:	Pereira, Felipe de Carvalho
Language :
Appears in Collections:	Repositório de Dados de Pesquisa da UNICAMP

Research data metasearch