Disseminating Information Across a Network: an Evolutionary Study

Abstract

The graph-burning problem is a significant issue in graph theory, and it has important applications in network science, particularly regarding weighted graphs. In this context, networks are modeled as graphs where nodes represent entities and edges denote connections with specific bandwidths, reflected in the weights that indicate message transmission times. The challenge involves efficiently disseminating a message from a central authority to all nodes, either directly or through neighboring nodes, while minimizing time. This paper aims to determine an optimal sequence that utilizes the fewest vertices for effective message spreading in weighted graphs. Given its NP-hard nature, this study generalizes two evolutionary algorithms to find optimal solutions and compare their effectiveness.