A Mathematical Formulation and Heuristic for the Message Propagation Problem in Connected Directed Graph

Fast and accurate propagation of leaders&quot messages is crucial in many organizations, and the propagation process can be modeled using graphical terms. When a connected graph is given, the propagation of the message from one node to all the other nodes is referred to as broadcasting. In this study, we introduce a new problem called the message propagation problem. We incorporated the requirements for the accuracy of the received message and the message propagation capacity into the classical network broadcasting problem. We propose a mathematical formulation and a heuristic to address the message propagation problem, and provide extensive computational results to demonstrate the performance of each approach. Our findings indicate that the formulation-based approach outperforms the heuristic in terms of message propagation time, while the heuristic shows great strength in terms of runtime and the average accuracy of the received message.