标题： k-环图中的广播改进近似 显示英文标题

标题： Improved Approximation for Broadcasting in k-cycle Graphs

摘要： 广播是一种信息传播原语，其中消息从一个节点（称为发起者）开始，并传递给网络中的所有其他节点。 广播研究的动机在于高效的网络设计以及确定标准网络拓扑的广播时间。 在任意网络$G$中验证节点$v$的广播时间已被证明是 NP-难的。 此外，最近的研究表明，在一般的仙人掌图和一些高度受限的仙人掌图子类中，广播时间问题也是 NP-完全的。 这些图族在结构上类似于$k$-环图，在其中广播时间问题也被认为是 NP-完全的。 在本文中，我们提出了一种简单的$(1.5-\epsilon)$-近似算法，用于确定使用$k$-环图建模的网络的广播时间，其中$\epsilon > 0$依赖于图的结构。 显示英文摘要

摘要： 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 also NP-complete in general cactus graphs and some highly restricted subfamilies of cactus graphs. These graph families are structurally similar to $k$-cycle graphs, in which the broadcast time problem is also believed to be NP-complete. In this paper, we present a simple $(1.5-\epsilon)$-approximation algorithm for determining the broadcast time of networks modeled using $k$-cycle graphs, where $\epsilon > 0$ depends on the structure of the graph.