

























Broadcasting is an information dissemination primitive where a message originates at a node (called the originator) and is passed to all other nodes in the network. Broadcasting research is motivated by efficient network design and determining the broadcast times of standard network topologies. Verifying the broadcast time of a node $v$ in an arbitrary network $G$ is known to be NP-hard. Additionally, recent findings show that the broadcast time problem is NP-hard in several highly restricted subfamilies of cactus graphs. The most restrictive of these families is known as \emph{$k$-cycle graphs} or \emph{flower graphs} and is the focus of this paper. We present a simple $(1.5-ε)$-approximation algorithm for determining the broadcast time of networks modeled using $k$-cycle graphs, where $ε> 0$ depends on the structure of the graph.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。