A Note to Non-adaptive Broadcasting

S Gholami, HA Harutyunyan - Parallel Processing Letters, 2024 - World Scientific
S Gholami, HA Harutyunyan
Parallel Processing Letters, 2024World Scientific
Broadcasting is a fundamental problem in the information dissemination area. In classical
broadcasting, a message must be sent from one network member to all other members as
rapidly as feasible. Although it has been demonstrated that this problem is NP-Hard for
arbitrary graphs, it has several applications in various fields. As a result, the universal lists
model, replicating real-world restrictions like the memory limits of nodes in large networks, is
introduced as a branch of this problem in the literature. In the universal lists model, each …
Broadcasting is a fundamental problem in the information dissemination area. In classical broadcasting, a message must be sent from one network member to all other members as rapidly as feasible. Although it has been demonstrated that this problem is NP-Hard for arbitrary graphs, it has several applications in various fields. As a result, the universal lists model, replicating real-world restrictions like the memory limits of nodes in large networks, is introduced as a branch of this problem in the literature. In the universal lists model, each node is equipped with a fixed list and has to follow the list regardless of the originator.
In this study, we focus on the non-adaptive branch of universal lists broadcasting. In this regard, we establish the optimal broadcast time of -ary trees and binomial trees under the non-adaptive model and provide an upper bound for complete bipartite graphs. We also improved a general upper bound for trees under the same model and showed that our upper bound cannot be improved in general.
World Scientific
以上显示的是最相近的搜索结果。 查看全部搜索结果