HUB-GA: A Heuristic for Universal Lists Broadcasting Using Genetic Algorithm

다국어 초록 (Multilingual Abstract)

Broadcasting is a fundamental problem in the infor-mation dissemination area. In classical broadcasting, a messagemust be sent from one network member to all other membersas rapidly as feasible. Although this problem is NP-hard forarbitrary graphs, it has several applications in various fields. As aresult, the universal lists model, which replicates some real-worldrestrictions like the memory limits of nodes in large networks, isintroduced as a branch of this problem in the literature. In theuniversal lists model, each node is equipped with a fixed list andhas to follow the list regardless of the originator.
As opposed to various applications for the problem of broad-casting with universal lists, the literature lacks any heuristic orapproximation algorithm. In this regard, we suggest HUB-GA:A heuristic for universal lists broadcasting with genetic algo-rithm, as the first heuristic for this problem. HUB-GA workstoward minimizing the universal lists broadcast time of a givengraph with the aid of genetic algorithm. We undertake variousnumerical experiments on frequently used interconnection net-works in the literature, graphs with clique-like structures, andsynthetic instances with small-world model in order to covermany possibilities of industrial topologies. We also compare ourresults with state-of-the-art methods for classical broadcasting,which is proved to be the fastest model among all. Neverthelessof the substantial memory reduction in the universal list modelcompared to the classical model, our algorithm finds the samebroadcast time as the classical model in diverse situations.